137. Evaluate Reverse Polish Notation

Reverse Polish Notation puts operators after their operands, which is exactly what a stack wants: push numbers, and when an operator appears, pop the top two, apply it, and push the result back.

Idea

In RPN, every operator acts on the two most recently seen values — a perfect match for a stack. Scan left to right: push each number; on an operator, pop the top two operands, combine them, and push the result. The final remaining value is the answer.

Order matters for - and /: the second popped value is the left operand. So pop b first, then a, and compute a op b.

Algorithm

1. Empty stack.
2. For each token:
   • If it's an operator: b = pop(), a = pop(), push a op b (integer division truncates toward zero).
   • Else: push int(token).
3. Return the single value left on the stack.

Worked example: ["2","1","+","3","*"]

Result: 9, i.e. (2 + 1) * 3.

Complexity

• Time: O(n) — each token processed once.
• Space: O(n) — the operand stack.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String tok : tokens) {
            switch (tok) {
                case "+": { int b = stack.pop(), a = stack.pop(); stack.push(a + b); break; }
                case "-": { int b = stack.pop(), a = stack.pop(); stack.push(a - b); break; }
                case "*": { int b = stack.pop(), a = stack.pop(); stack.push(a * b); break; }
                case "/": { int b = stack.pop(), a = stack.pop(); stack.push(a / b); break; }
                default: stack.push(Integer.parseInt(tok));
            }
        }
        return stack.pop();
    }
}