Evaluate RPN
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. Division between two integers should truncate toward zero. The given RPN expression is always valid.
- 1 <= tokens.length <= 10⁴
- tokens[i] is either an operator (+, -, *, /) or an integer in range [-200, 200]
- Division truncates toward zero; expression is always valid
tokens = ["2","1","+","3","*"]9tokens = ["4","13","5","/","+"]6tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]22Normal math writes the operator between its two numbers: 3 + 4. Reverse Polish Notation writes it after them: 3 4 +. Reading left to right, when you finally reach that +, the two numbers it should combine are the two you saw most recently. So you need somewhere to stash numbers as they arrive and, the instant an operator appears, grab the two newest ones.
"Grab the most recent items first" is exactly what a stack gives you. A stack is a pile you can only touch from the top: push adds a value on top, pop removes the top one, and the last value pushed is the first popped ("Last In, First Out"). Keep the waiting numbers on a stack and the operators fall into place.
The scan is short. For each token:
- A number → push it onto the stack.
- An operator → pop the top two numbers, combine them, and push the single result back. That result may itself become an operand for a later operator — exactly like a closed bracket collapsing into the expression around it.
When the tokens run out, one number is left on the stack: the answer.
def eval_rpn(tokens):
ops = {'+', '-', '*', '/'}
stack = []
for t in tokens:
if t not in ops:
stack.append(int(t))
else:
right = stack.pop() # first popped is the RIGHT operand
left = stack.pop() # second popped is the LEFT operand
if t == '+': stack.append(left + right)
elif t == '-': stack.append(left - right)
elif t == '*': stack.append(left * right)
else: stack.append(int(left / right)) # truncate toward zero
return stack.pop()+ and * this is harmless, but 13 5 / means 13 / 5, not 5 / 13 — swap them and subtraction and division silently give wrong answers. Also use int(left / right), not left // right: the problem wants truncation toward zero, but // in Python rounds toward negative infinity, so -7 // 2 is -4 when the required answer is -3.4 push → [4] · 13 push → [4, 13] · 5 push → [4, 13, 5]/ → pop right=5, left=13; 13 / 5 = 2; push → [4, 2]+ → pop right=2, left=4; 4 + 2 = 6; push → [6]Pushing the result back is the load-bearing move: a finished sub-expression becomes a single number that waits its turn like any other, so one left-to-right pass evaluates the whole expression — each operator always finds its two operands sitting right on top.
Reverse Polish Notation Mechanics
Intuition
- Post-Order Logic: In RPN, operators follow their operands. The stack naturally holds operands until an operator arrives.
- The Order of Popping: The first popped item is the right operand (b), and the second is the left (a).
- Recursive Nature: Each result pushed back to the stack becomes an operand for a future operator.
RPN Strategy
Scan the tokens from left to right. If the token is a number, push it to the stack. If it is an operator, pop the two most recent numbers, apply the operator, and push the result back. At the end, the stack will contain exactly one value: the final result.