In traditional arithmetic, we write math expressions using infix notation, where operators are placed between operands, such as 3 + 4 or (5 - 2) * 8. While intuitive for humans, infix notation is complicated for compilers to parse. It requires parentheses to define operator precedence and complex parsing algorithms (like Shunting-yard) to resolve order.

To simplify parsing, computer systems often use Reverse Polish Notation (RPN), or postfix notation. In RPN, operators follow their operands: 3 4 + or 5 2 - 8 *. The major benefit of RPN is that it entirely eliminates parentheses because the order of evaluation is completely unambiguous.

Our goal is to write a Java program that evaluates a valid RPN expression. The supported operators are addition (+), subtraction (-), multiplication (*), and division (/). The division operation must perform integer division, truncating the result toward zero.

Illustration of evaluating Reverse Polish Notation using a Stack in Java
Real-World Analogy: The Accountant's Desk Stack

To understand postfix evaluation, imagine working as an accountant with a clean desk. You maintain a single stack of sheets, putting new sheets on top of old ones.

Your client delivers sheets to your desk one by one:

  • If the sheet contains a numeric value (an operand), you simply place it on top of your paper stack.
  • If the sheet contains an action command (an operator like '+' or '*'), you reach for the top two sheets on your stack, perform the calculation, write the result on a fresh sheet, discard the two source sheets, and place the new result sheet back on top of the stack.
  • Once the client stops delivering papers, the final answer to the entire calculation is the single sheet of paper remaining on your desk.
In software, this desk pile represents a LIFO (Last-In, First-Out) Stack data structure.

Stack-Based Evaluation Strategy

Because RPN evaluates operators as soon as their operands are available, a Stack is the perfect matching structure:

  • We loop through the array of tokens.
  • When we encounter an operand, we convert the string token to an integer and push it onto our stack.
  • When we encounter an operator:
    • We pop the top two numbers from the stack. Let the first popped element be b (the right operand) and the second popped element be a (the left operand). Note: The popping order is critical for non-commutative operations like subtraction and division (we compute a - b and a / b respectively).
    • We execute the math operation.
    • We push the result back onto the stack.
Once all tokens are processed, the stack will contain exactly one number, which represents our final evaluation.

Step-by-Step Scenario Walkthrough

Let's trace the stack states for tokens = ["4", "13", "5", "/", "+"]:

  1. Token "4": It is a number. Push it. Stack state: [4].
  2. Token "13": It is a number. Push it. Stack state: [4, 13].
  3. Token "5": It is a number. Push it. Stack state: [4, 13, 5].
  4. Token "/": It is a division operator.
    • Pop right operand: b = 5.
    • Pop left operand: a = 13.
    • Calculate: 13 / 5 = 2 (truncating integer division).
    • Push result 2. Stack state: [4, 2].
  5. Token "+": It is an addition operator.
    • Pop right operand: b = 2.
    • Pop left operand: a = 4.
    • Calculate: 4 + 2 = 6.
    • Push result 6. Stack state: [6].
The token array is empty. We pop and return the final remaining value: 6.

Key Code Explanations

Here is why the main logic in the solution is important:

  • int b = stack.pop(); int a = stack.pop();: Popping the right operand first and the left operand second. This guarantees the correct order for non-commutative operations like division and subtraction.
  • switch (operator): Efficiently routes execution to the correct arithmetic operation based on the operator symbol.
  • Integer.parseInt(token): Parses string tokens into integer representations for mathematical computation.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;
 
import java.util.Stack;
 
public class EvaluateRPN {
 
    // Stack evaluation: Time O(N), Space O(N)
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();
                int result = applyOperator(token, a, b);
                stack.push(result);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
 
    private boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }
 
    private int applyOperator(String operator, int a, int b) {
        switch (operator) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            default: throw new IllegalArgumentException("Unknown operator: " + operator);
        }
    }
 
    public static void main(String[] args) {
        EvaluateRPN solver = new EvaluateRPN();
        String[] tokens = {"4", "13", "5", "/", "+"}; // 4 + (13 / 5) = 4 + 2 = 6
 
        System.out.println("--- Evaluate Reverse Polish Notation Demonstration ---");
        System.out.println("Tokens: [4, 13, 5, /, +]");
        System.out.println("Result: " + solver.evalRPN(tokens));
    }
}

Conclusion & Complexity Analysis

This stack-based RPN solver is highly efficient, running in O(N) time complexity since we iterate through the tokens list exactly once. It uses O(N) space complexity to store operands in the stack. By utilizing the LIFO property of stacks, we evaluate postfix arithmetic expressions cleanly, avoiding the complexity of operator priority parsing.