You are given a list of strings called tokens. Together they form a sum written in Reverse Polish Notation, or RPN. In RPN, each operator comes after the two numbers it works on. So 2 + 1 is written as 2 1 +. Work out the value of the whole expression and return it.
The operators are +, -, * and /. Division keeps only the whole-number part, rounding toward zero. So 13 / 5 = 2.6 becomes 2, and -13 / 5 = -2.6 becomes −2 (not −3).
There are up to 10,000 tokens. Each number is between −200 and 200. The expression is always valid, and there is never a division by zero.
In normal writing, 2 + 3 * 4 needs rules to tell you that * goes first. You need brackets to change that order: (2 + 3) * 4. RPN needs neither. The order of the tokens already decides the order of the work. That is why it exists.
Here is how to read RPN by hand. Go left to right. When you meet an operator, it works on the two most recent numbers that have not been used yet. Replace those two numbers and the operator with the result, and carry on.
"The two most recent" is the clue. A structure that always hands back the most recent item first is a stack, a pile where you only add to and take from the top.
Do exactly what you would do by hand on paper. Find the first operator, combine the two numbers just before it, put the result in their place, and start scanning again from the beginning.
python
def evalRPN(tokens): tokens = tokens[:] while len(tokens) > 1: for i, t in enumerate(tokens): if t in "+-*/" and len(t) == 1: a, b = int(tokens[i - 2]), int(tokens[i - 1]) r = {"+": a + b, "-": a - b, "*": a * b, "/": int(a / b)}[t] tokens[i - 2:i + 1] = [str(r)] # three tokens become one break return int(tokens[0])
Each step rebuilds the list and rescans from the start. With 10,000 tokens that is O(n^2).
The waste in one sentence: after every operation it rescans from the beginning, when the two numbers it needs next are always the two most recent ones.
An operator pops the top two numbers, combines them, and pushes the result back.
At the end, the stack holds exactly one number: the answer.
Which popped number is which matters. The first number you pop is the one pushed last, so it is the right-hand number. For 13 5 / you pop 5 first, then 13, and compute 13 / 5, not 5 / 13. For + and * the order does not matter, which is why getting it wrong passes half the tests and fails the rest.
(1) A table from each operator to what it does. Each value is a small function written with lambda, which is Python's way of writing a one-line function without a name. lambda a, b: a + b means "a function that takes a and b and returns their sum".
A table like this is called a dispatch table. It replaces a chain of if/elif checks. Adding a new operator is one new line in the table, not a new branch in the loop. It is the smallest form of the Strategy pattern from 9.4.12.
(2) Division that rounds toward zero. This line is where most wrong answers to this problem go wrong.
Python's // operator rounds down, toward negative infinity. So -13 // 5 is −3. But the problem wants rounding toward zero, which gives −2. The fix is int(a / b). a / b gives the decimal -2.6, and int() in Python simply drops the decimal part, giving −2.
For positive numbers the two methods agree. That is why this bug hides until a test uses a negative number.
Expression
Python //
int(a / b)
Correct here
13 / 5
2
2
2
−13 / 5
−3
−2
−2
JavaScript has the same trap in a different spot. / gives a decimal, and Math.floor(-2.6) is −3. Math.trunc drops the decimal part, which rounds toward zero.
(3) The stack of numbers waiting to be used.
(4) Walk the tokens once, left to right.
(5) Is this token an operator? We check whether it is one of the table's keys. This is safer than checking whether the token "looks like a number". The token "-4" starts with a minus sign, but it is a number, not the operator -. Checking against the table avoids that confusion.
(6) Pop the two numbers, right-hand one first.b is popped first because it was pushed last, so it is the right-hand number. a is the left-hand number.
(7) Combine them and push the result.ops[t] looks up the function for this operator, and (a, b) calls it. The result goes back on the stack, ready to be used by a later operator.
(8) A number.int(t) turns the text "13" into the number 13, and we push it.
(9) The answer. The expression is valid, so exactly one number is left.
Time. We visit each of the n tokens once. A number costs one conversion and one push. An operator costs two pops, one arithmetic step and one push. Each of those is constant time. So the total is O(n).
Space. In the worst case, many numbers come before the operators, like ["1", "2", "3", "4", "+", "+", "+"]. Then about half the tokens sit on the stack at once. That is O(n).
RPN is not just a puzzle. It is the form that sums take inside computers.
Turning normal notation into RPN. The shunting-yard algorithm reads 2 + 3 * 4 and writes 2 3 4 * +, using a second stack to hold operators until it knows their order. Run this page's code on the result, and you have a full calculator.
Stack machines. Many programming languages compile your code into simple instructions for a "stack machine". An instruction like "add" pops two numbers and pushes their sum, exactly like line (7). Java and WebAssembly both work this way.
Basic Calculator (LeetCode 224 and 227). Work out a normal sum with brackets and * before +, directly from the string. Harder, and it uses the same stack ideas.
The general lesson: when each operation uses the most recent results, use a stack.
"Which popped number is the left one?" The second one popped. Say it before you write the lines.
"Why not // in Python?" It rounds down, not toward zero. Give −13 / 5 as the example.
"How would you handle normal notation, like 2 + 3 * 4?" The shunting-yard algorithm: one list for output, one stack for operators. Before pushing an operator, pop any operators already on the stack that should happen first.
"What if the input could be invalid?" An operator could find fewer than two numbers on the stack, or more than one number could be left at the end. A real calculator checks both and reports where the error is.
"Why a table instead of if/elif?" Adding an operator is one line. For example, a power operator is "^": lambda a, b: a ** b. The loop itself never changes.
One thing to volunteer: mention that stack machines inside real programming languages run their instructions exactly like this. It turns the puzzle into something real.
Next:4.8.4 Generate Parentheses. Despite its place in this group, it is not a stack problem. It is the first backtracking problem in the book.