The problem
Evaluate an arithmetic expression written in Reverse Polish Notation, where each operator comes after its two numbers (e.g. “2 1 +” means 2 + 1). Division truncates toward zero.
Input: ["2", "1", "+", "3", "*"] Output: 9 ((2 + 1) × 3)
Picture it
Picture a calculator made of a stack of plates. Each number is written on a plate and put on top. When an operator arrives, take off the top two plates, combine them, and put the result back as one plate. When the tokens run out, the last plate is the answer.
How to recognise it
- The input is a list of tokens where each operator comes after its operands, so no brackets or precedence rules are needed.
- Every operator works on the two most recent results that have not been used yet. "Most recent first" is what a stack gives you.
- Each intermediate result becomes an operand for a later operator, so results must go back where the next operator can find them.
- Up to 10^4 tokens, so one left-to-right pass is expected.
Start with brute force
Find the first operator in the list. Because the expression is valid, the two tokens just before it are numbers. Replace those three tokens with the result and repeat until one token is left.
def eval_rpn_brute(tokens):
tokens = list(tokens)
while len(tokens) > 1:
i = next(k for k, t in enumerate(tokens) if t in OPS) # first operator
a, b = int(tokens[i - 2]), int(tokens[i - 1])
tokens[i - 2:i + 1] = [str(OPS[tokens[i]](a, b))]
return int(tokens[0])
Each round removes one operator, but finding it and rebuilding the list costs O(n). With about n/2 operators that is O(n²) time: roughly 5 × 10^3 rounds over a list of up to 10^4 tokens, so around 5 × 10^7 steps. Space is O(n) for the copy.
From brute force to the idea
- Find the waste. Each round rescans from the start to find the next operator, even though everything before the previous result has not changed.
- Keep the unused results in order. As you read left to right, every number (or computed result) waits until an operator needs it. The operator always needs the two newest ones: that is the top of a stack.
- Numbers are pushed.
stack.append(int(t)). A token like"-3"is not inOPS, so it is parsed as a negative number; only the single character"-"is the operator. - Operators pop twice, in the right order. The first pop is the right operand
b, the second is the left operanda. Order matters for-and/. - Divide toward zero.
int(a / b)truncates toward zero, as the problem asks. Python'sa // brounds down instead, so-7 // 2is −4 but the answer needs −3. - The result is the last item. A valid expression leaves exactly one value, so
stack[0]is the answer.
This is the key idea: an operator always uses the two latest unused values, which are the top two items on a stack.
The key idea
Numbers push; operators pop two, compute, push the result. One pass with a stack, O(n).
Python solution
OPS = {"+": add, "-": sub, "*": mul, "/": lambda a, b: int(a / b)}
def eval_rpn(tokens):
stack = []
for t in tokens:
if t in OPS:
b = stack.pop()
a = stack.pop()
stack.append(OPS[t](a, b))
else:
stack.append(int(t))
return stack[0]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from operator import add, sub, mul
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): about n/2 rounds, each scanning and rebuilding the list | O(n): the token copy |
| Stack (shown code) | O(n): each token is pushed once and popped at most once | O(n): up to about n/2 numbers wait on the stack |
Edge cases
- Imports: the shown code uses
add,subandmulwithout importing them; it needsfrom operator import add, sub, mul, or definingOPSraisesNameError. - A single number (
["5"]): nothing is popped, returns 5. - Negative division (
["-7", "2", "/"]): returns −3, truncated toward zero. - Negative numbers as tokens (
["3", "-4", "-"]): returns 7, because"-4"is read as a number. - Huge numbers:
int(a / b)goes through a float, which is exact only up to about 2^53.["10000000000000000001", "1", "/"]gives 10^19, not 10^19 + 1. LeetCode keeps every value within 32 bits, where this is safe. - Division by zero raises
ZeroDivisionError; the problem promises it never happens.
Common mistakes
- Popping
afirst andbsecond, which turns13 4 -into 4 − 13 instead of 13 − 4. - Using
//for division, which rounds toward minus infinity and is wrong whenever the result is negative and not whole. - Testing
t.isdigit()to spot numbers, which treats"-3"as an operator. - Pushing the token strings without
int(). Thenadd("2", "1")joins them into"21"instead of adding.
Now every operator comes before its two operands: ["*", "+", "2", "1", "3"] means (2 + 1) × 3 = 9. Evaluate it with the same stack idea. Describe your approach, then write it if you like.
Compare with our answer
Read the tokens from right to left. Then operands are seen before the operator that uses them, just as in RPN. The difference is the pop order: the first pop is now the left operand.
def eval_pn(tokens):
stack = []
for t in reversed(tokens):
if t in OPS:
a = stack.pop() # left operand comes off first
b = stack.pop()
stack.append(OPS[t](a, b))
else:
stack.append(int(t))
return stack[0]
eval_pn(["-", "10", "3"]) is 7. Time O(n), space O(n).
A strong answer mentions: scanning in reverse, why the pop order flips compared with RPN, and a test with - or / where swapping the operands would change the answer.
1. A spreadsheet stores formulas in postfix form and adds a max token that takes two values. Which approach fits best?
A two-argument function in postfix behaves exactly like +: it uses the two newest values. The stack handles it in O(n); repeated replacement is O(n²), and eval on built strings is slow and unsafe.
2. Why does the shown code pop b before a?
In 13 5 /, the 5 is pushed after the 13, so it is on top. pop() takes from the end of the list. Subtraction and division are not commutative, so the order matters.
3. A learner replaces the division lambda with lambda a, b: a // b. Which input now gives a wrong answer?
-7 // 2 rounds down to −4, while truncating toward zero gives −3. The other divisions are either positive or exact, where both rules agree.
Score 60% or more and the lesson is marked complete.