Evaluate a Reverse-Polish-Notation Expression
You are given an arithmetic expression in Reverse Polish Notation (RPN) as a list of string tokens. Each token is either an integer literal (a possibly-negative base-10 integer) or one of the four binary operators +, -, *, /. Evaluate the expression and return the resulting integer.
Processing rule: scan left to right; push every integer literal onto a stack; on an operator pop the top two values b (popped first, the right operand) and a (the left operand), push a OP b. Division / is integer division that TRUNCATES TOWARD ZERO (the C/C++ convention), e.g. (-7)/2 == -3 and 7/(-2) == -3. The expression is guaranteed valid (no underflow, no division by zero) and reduces to exactly one value, which you return.
Complete: ``` rpn_eval(tokens: List[str]) -> int ``` Example: ['2','1','+','3','*'] is (2+1)*3 = 9.
Hints
- Use an explicit stack: push integer literals, and on an operator pop the two most recent operands.
- Order matters: the FIRST value popped is the right operand. For division, truncate toward zero with int(a/b), not Python's floor //.
Worked Solution
How to Think About It: RPN evaluation is the canonical stack-machine exercise: postfix needs no parentheses because operator order already encodes precedence — you just push operands and let each operator consume the top two. The one genuine trap is operand order: the value popped *first* is the *right* operand $b$, the one popped *second* is the *left* operand $a$, so you compute $a\ \text{OP}\ b$, not $b\ \text{OP}\ a$. This is invisible for $+$ and $*$ but flips the sign of $-$ and inverts $/$. The second trap is truncation toward zero: Python's // *floors* (rounds toward $-\infty$), so $-7\,//\,2 = -4$, but the C-convention answer is $-3$. Use int(a / b), which truncates toward zero. Naming: -3 as a literal is a valid token, so the "is it an operator?" test must check membership in the operator set, not "does it start with a digit."
Quick Estimate: Trace ['2','1','+','3','*'] on paper-in-your-head. Push $2$, push $1$; + pops $b=1$, $a=2$, pushes $a+b=3$; push $3$; * pops $b=3$, $a=3$, pushes $9$. Stack $=[9]$ $\Rightarrow 9$. Now stress the two traps: ['-7','2','/'] $\to$ $a=-7,b=2$, int(-7/2)=int(-3.5)=-3 (floor would give $-4$ — wrong); ['7','-2','/'] $\to$ `int(7/-2)=int(-3.5)=-3$. Both match the C convention. All verified in Python.
Approach: Left-to-right scan; operators pop two (right then left), literals push int(token); truncate division with int(a/b).
Formal Solution: ```python def rpn_eval(tokens): st = [] for t in tokens: if t in ('+', '-', '*', '/'): b = st.pop(); a = st.pop() # b = right, a = left if t == '+': st.append(a + b) elif t == '-': st.append(a - b) elif t == '*': st.append(a * b) else: st.append(int(a / b)) # truncate toward zero else: st.append(int(t)) # handles negative literals return st[-1] ``` Invariant: after processing a prefix of tokens, the stack holds exactly the values of the maximal already-reduced subexpressions, top = most recent. A valid RPN expression leaves exactly one value, returned as st[-1]. Membership test t in ('+','-','*','/') correctly classifies '-3' as a literal (it is not equal to '-').
$$\text{time } O(n),\qquad \text{space } O(n)\ \text{(stack depth)}.$$
Answer: Stack-evaluate with right-then-left pops and toward-zero division; the example gives $\boxed{9}$.
Intuition
RPN removes the need for parentheses and precedence: each operator simply consumes the two operands immediately preceding it, which a stack models exactly.