Evaluate Reverse Polish Notation.

Problem. Evaluate an arithmetic expression in Reverse Polish Notation (postfix), given as tokens. Operators + - * / are binary; division truncates toward zero. Example: ["2","1","+","3","*"] → (2+1)*3 = 9.

Why a stack is the natural fit

RPN was designed for stack evaluation — it is how stack-based calculators and the JVM bytecode interpreter work. There are no parentheses and no precedence rules to parse: operands pile up, and each operator consumes the top two values and pushes the result back. No brute-force/optimal split here — the stack solution is the solution, in a single O(n) pass.

int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+" -> stack.push(stack.pop() + stack.pop());
            case "*" -> stack.push(stack.pop() * stack.pop());
            case "-" -> {
                int b = stack.pop(), a = stack.pop();   // order matters!
                stack.push(a - b);
            }
            case "/" -> {
                int b = stack.pop(), a = stack.pop();
                stack.push(a / b);                       // Java int / truncates toward 0
            }
            default -> stack.push(Integer.parseInt(t));  // operand
        }
    }
    return stack.pop();   // the single remaining value is the answer
}