Introduction & Problem Explanation

The Evaluate Reverse Polish Notation (RPN) problem (often referred to as Postfix Notation) requires us to evaluate the value of an arithmetic expression represented in a postfix format.

In standard math (infix notation), we write operators between numbers, like 3 + 4 or (2 + 1) * 3. This requires parentheses to establish order of operations. In Reverse Polish Notation, the operators follow their operands, like 3 4 + or 2 1 + 3 *. The major advantage of RPN is that it completely eliminates the need for parentheses because the order of operations is unambiguous. Our goal is to compute the final integer result of a valid RPN expression. The valid operators are '+', '-', '*', and '/'. Division between two integers should truncate toward zero.

Illustration of evaluating Reverse Polish Notation using a Stack in Java
Real-World Analogy: The Calculator's Paper Trail Stack

Imagine you are accountant with a physical stack of papers. Every time a client hands you a receipt with a dollar value (a number), you place it on top of your stack. When they hand you an instruction card (like "add" or "multiply"), you reach for the top two sheets of paper, perform the math, write down the result on a new sheet of paper, throw away the used sheets, and place the new result back on top of the stack. When the clients stop handing you items, the final result will be the single sheet of paper remaining on your desk.

The Algorithmic Approach

Stack-Based Postfix Evaluation (O(n) Time, O(n) Space)

Since RPN process operators immediately after their operands, a Stack is the ideal data structure because of its Last-In, First-Out (LIFO) property.

  • We iterate through each token in the input array.
  • If the token represents an operand (a number), we convert it to an integer and push it onto the stack.
  • If the token is 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: Order is critical for subtraction and division (i.e., a - b and a / b).
    • We apply the corresponding arithmetic operation.
    • We push the resulting value back onto the stack.
After reading all tokens, the stack will contain exactly one value, which is the final answer.

Step-by-Step Execution Walkthrough

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

  1. Step 1 (Initialization): Create an empty stack: stack = [].
  2. Step 2 (Token: "4"): It's a number. Push it.
    • Stack state: [4]
  3. Step 3 (Token: "13"): It's a number. Push it.
    • Stack state: [4, 13]
  4. Step 4 (Token: "5"): It's a number. Push it.
    • Stack state: [4, 13, 5]
  5. Step 5 (Token: "/"): It's an operator.
    • Pop top: b = 5.
    • Pop next: a = 13.
    • Compute: 13 / 5 = 2 (truncated toward zero).
    • Push result: 2.
    • Stack state: [4, 2]
  6. Step 6 (Token: "+"): It's an operator.
    • Pop top: b = 2.
    • Pop next: a = 4.
    • Compute: 4 + 2 = 6.
    • Push result: 6.
    • Stack state: [6]
  7. Step 7 (Final Check): No more tokens left. Pop and return the final remaining value: 6.

Key Code Snippets & 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 (token): 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

Evaluating Reverse Polish Notation is a classic problem showcasing how a Stack simplifies computation. By using standard stack operations, we evaluate complex postfix mathematical expressions in linear O(n) time without dealing with order of operations or brackets.