Evaluate Reverse Polish Notation — Solution

Problem

Given a list of string tokens representing a mathematical expression in Reverse Polish Notation (RPN), compute and return the integer result. In RPN, every operator follows its operands, so 3 4 + means 3 + 4 = 7 — no parentheses or precedence rules needed.

• Input: ["2","1","+","3","*"]
• Output: 9
• Explanation: (2 + 1) * 3 = 9

Division always truncates toward zero: ["6","2","/"] returns 3, and ["7","-2","/"] returns -3 (not -4).

Intuition

RPN was invented specifically so that expressions can be evaluated with a single left-to-right scan using a stack. Every time you see an operator, the two values it needs are sitting right at the top of the stack — the most recently pushed unapplied operands. No backtracking or precedence resolution is ever needed.

Solution — Stack-Based Evaluation

Scan tokens left to right, pushing numbers onto a stack. When an operator is encountered, pop the top two values (right operand first, then left), compute the result, and push it back.

1. Initialize an empty stack.
2. For each token in the list:
   • If it is a number, convert to int and push onto the stack.
   • If it is an operator, pop right, then pop left.
3. Apply the operator to left and right and push the result.
4. For division, use truncation toward zero (not floor division).
5. Return the single value remaining on the stack.

1def evalRPN(tokens: list[str]) -> int:
2    stack = []
3    for token in tokens:
4        if token in {'+', '-', '*', '/'}:
5            right = stack.pop()
6            left = stack.pop()   # pushed before right, so it's the left operand
7            if token == '+':
8                stack.append(left + right)
9            elif token == '-':
10                stack.append(left - right)
11            elif token == '*':
12                stack.append(left * right)
13            else:
14                stack.append(int(left / right))  # int() truncates toward zero; // would floor
15        else:
16            stack.append(int(token))
17    return stack[0]

Time: O(n) — one pass through the token list, each with O(1) stack operations.
Space: O(n) — in the worst case (all numbers precede all operators), the stack holds up to ⌊n/2⌋ + 1 values.

Complexity Summary

Common Mistakes

• Popping operands in the wrong order — the first pop() gives the right operand, not the left; for ["3","2","-"] popping carelessly and computing right - left gives -1 instead of the correct 1.
• Using Python's // for division — // floors toward negative infinity, so 6 // -132 is -1, but truncating toward zero gives 0; always use int(left / right) for this problem.
• Mistaking a negative number token for the minus operator — a token like "-11" is a two-character string and correctly falls through to int(token); the operator check on a single "-" is not triggered.
• Assuming all operands are single-digit — tokens can be multi-digit integers and negative numbers; use int() or parseInt(), never character arithmetic.
• Returning stack[-1] before all tokens are processed — the final answer is only guaranteed correct after the entire token list is consumed.

Related Problems

• decode-string — uses a stack to process bracketed expressions with nested depth, same push/pop rhythm
• valid-parentheses — foundational stack matching; recognizing when to pop is the same intuition
• largest-rectangle-in-histogram — monotonic stack where each pop triggers a computation, similar to the operator-triggered pops here
• remove-k-digits — stack used to greedily build a result by deciding what to pop on each new token
• daily-temperatures — monotonic stack where a new value triggers resolution of previously pushed entries