Evaluate Reverse Polish Notation Using a Stack

• Postfix notation – each operator follows its two operands, removing ambiguity without parentheses.
• Stack-based evaluation – push numbers; on operators, pop two, compute, push result.
• Operand order – first pop is right operand, second pop is left operand.
• O(n) time – each token is processed once.
• Division safety – for BigDecimal, always specify scale and RoundingMode to prevent ArithmeticException.

What is Reverse Polish Notation?

Reverse Polish Notation (RPN), also called postfix, writes each operator after its two operands. For example, the infix expression (3 + 4) * 2 becomes 3 4 + 2 * in postfix. There are no parentheses and no precedence rules because the position of the operator already fixes the evaluation order.

How does stack-based evaluation work?

Scan tokens left to right. If a token is a number, push it. If it is an operator, pop the top two values, apply the operator, and push the result. When all tokens are consumed, the single value on the stack is the answer.

package com.bank.service;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayDeque;
import java.util.Deque;

public class FeeCalculator {

    public static BigDecimal evaluateRPN(String[] tokens) {
        Deque<BigDecimal> stack = new ArrayDeque<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                case "-":
                case "*":
                case "/":
                    BigDecimal right = stack.pop();
                    BigDecimal left = stack.pop();
                    BigDecimal result;
                    switch (token) {
                        case "+": result = left.add(right); break;
                        case "-": result = left.subtract(right); break;
                        case "*": result = left.multiply(right); break;
                        case "/": result = left.divide(right, 2, RoundingMode.HALF_UP); break;
                        default: throw new IllegalArgumentException("Unknown op: " + token);
                    }
                    stack.push(result);
                    break;
                default:
                    stack.push(new BigDecimal(token));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        // Formula: (principal * rate / 100) + processingFee
        // Postfix: principal rate * 100 / processingFee +
        String[] tokens = {"100000", "8.5", "*", "100", "/", "500", "+"};
        BigDecimal fee = evaluateRPN(tokens);
        System.out.println("Computed fee: Rs." + fee);
    }
}

Computed fee: Rs.9000.00

Why does operand order matter?

When you pop, the first value off the stack is the right operand and the second is the left. For addition and multiplication, order does not matter because they are commutative. For subtraction and division, swapping the operands gives the wrong result. Always pop right first, then left.

// For tokens: 10 3 -
// Stack after pushes: [10, 3] (3 on top)
// Pop right = 3, pop left = 10
// Result = 10 - 3 = 7 (correct)
// Wrong: 3 - 10 = -7 (incorrect)

Why use BigDecimal for money calculations?

Double arithmetic introduces rounding errors. For fee calculations, BigDecimal stores the exact decimal value. Division must specify a scale and rounding mode, otherwise a non-terminating decimal like 10 / 3 throws an ArithmeticException.

// Wrong: no scale specified
left.divide(right); // throws ArithmeticException for 10/3

// Correct: specify scale and rounding
left.divide(right, 2, RoundingMode.HALF_UP); // 3.33

What is the time and space complexity?

• Time: O(n) where n is the number of tokens, because each token is processed once.
• Space: O(n) for the stack in the worst case (all operands before any operator).

Where does postfix notation come from?

Compilers convert infix to postfix using the shunting-yard algorithm so that evaluation becomes this trivial stack pass. Stack-based virtual machines, including the JVM's operand stack, execute arithmetic bytecode the same way.

What are common mistakes?

The most common mistake is popping operands in the wrong order, producing right - left instead of left - right. Another is forgetting to specify the rounding mode for BigDecimal division.

How does this extend to more complex expressions?

The same stack approach handles unary operators (push a marker), functions (pop the correct number of arguments), and variables (look up the value before pushing). The shunting-yard algorithm handles converting any infix expression to postfix, including precedence and associativity.

What should a senior engineer know?

A senior engineer knows that postfix evaluation is not academic: it is the execution model of the JVM itself. Every arithmetic operation in Java bytecode pushes and pops from the operand stack. The senior also knows that storing fee formulas in postfix in the database allows the pricing engine to evaluate them with this simple stack pass on the hot path, without parsing infix at runtime.