Evaluate Reverse Polish Notation

Reverse Polish Notation puts operators after their operands: 2 1 + means 2 + 1. The machine evaluates the whole expression left to right with no parentheses and no precedence rules — the notation already encodes order.

The key insight: operands go on a stack, and every operator consumes the top two. When the machine hits an operator it pops b then a — careful, pop order matters: division and subtraction are not commutative — computes a op b, and pushes the result. At the end, the single remaining stack value is the answer. Integers may be negative, and division truncates toward zero.

Approach in steps:

1. Push every token that is an operand.
2. On an operator, pop b, then a, compute, push the result.
3. Return stack[0].

def evalRPN(tokens):
    stack = []
    for t in tokens:
        if t in "+-*/":
            b = stack.pop()
            a = stack.pop()
            if t == "+":
                stack.append(a + b)
            elif t == "-":
                stack.append(a - b)
            elif t == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))
        else:
            stack.append(int(t))
    return stack[-1]

Time is O(n), space O(n) for the stack.

Trickiest edge case: division of negatives. -7 / 2 must truncate toward zero to -3 — Python's / gives -3.5, so the machine must call int(). Floor division // would give -4, the wrong answer. Integer overflow is irrelevant here (Python ints are unbounded), but C-style languages need 32-bit wraps.