Evaluate Reverse Polish Notation
Problem statement
You get a list of tokens that make up an arithmetic expression written in Reverse Polish Notation (RPN), also called postfix notation. In RPN every operator comes after its two operands instead of between them. For example, 2 + 1 is written as the tokens ["2", "1", "+"]. Work out the value of the whole expression and return it as an integer.
Each token is either a number or one of +, -, *, /. Division between two integers always truncates toward zero, so 13 / 5 is 2 and -13 / 5 is -2, not -3. The input is always a valid RPN expression, and every intermediate result fits in a 32-bit integer.
RPN is used when an expression must be evaluated mechanically, without operator precedence rules or parentheses. A calculator's internal form or a query planner's compiled filter can look like this.
Examples
Example 1
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: "2" and "1" are operands, and "+" combines them into 3. Then "3" is the next operand, and "*" multiplies: (2 + 1) * 3 = 9.
Example 2
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: "/" combines 13 and 5 first, giving 2 (truncated toward zero). Then "+" combines 4 and 2: 4 + 2 = 6.
Example 3
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: From the inside out: 9 + 3 = 12, then 12 * -11 = -132, then 6 / -132 = 0 (truncated toward zero), then 10 * 0 = 0, then 0 + 17 = 17, and finally 17 + 5 = 22.
Hints
Approach
Optimal: Recursion from the back
Intuition
Let the language's call stack do the job of the explicit stack. Walk the tokens from the end backward. The last token is always the outermost operator, or the whole expression is a single number. A number is returned as it is. An operator needs two operands, and the tokens just before it, read backward, are those operands. Each operand may itself be a whole sub-expression, so evaluate the right operand first (it is closer to the end), then the left, then combine them. This gives the same answer and cost as the stack, and is worth knowing for the common follow-up "do it without an explicit stack".
Steps
- Keep an index
idxpointing at the last token. - Read the token at
idx, then moveidxone step earlier. - If the token is a number, return it.
- If it is an operator, recursively evaluate the right operand first, then the left operand.
- Return
left OP right. - The first call returns the value of the whole expression.
Dry run
tokens = ["2","1","+","3","*"], idx starts at 4
| idx read | token | action |
|---|---|---|
| 4 | "*" | operator, so evaluate right then left |
| 3 | "3" | number, returns 3 (the right operand of "*") |
| 2 | "+" | operator, so evaluate right then left (this is the left operand of "*") |
| 1 | "1" | number, returns 1 (the right operand of "+") |
| 0 | "2" | number, returns 2 (the left operand of "+") |
Unwinding: "+" gives 2 + 1 = 3, then "*" gives 3 * 3 = 9.
Edge cases: the right operand must be read before the left one, because idx moves backward and the right operand is nearer the end. Reading them in the other order would swap the operands, which breaks - and /.
Complexity
Time O(n) - Each token is consumed exactly once across the whole recursion. Every call does a constant amount of work besides its two recursive calls. So the total is proportional to the number of tokens.
Space O(n) - There is no explicit stack, but the call stack grows as deep as the expression is nested. In the worst case, a long chain of operators, that depth is proportional to n. Very deep recursion can hit a language's call-stack limit.
OPERATORS = {"+", "-", "*", "/"}
class Solution:
def evalRPN(self, tokens: list[str]) -> int:
idx = len(tokens) - 1
def helper() -> int:
nonlocal idx
token = tokens[idx]
idx -= 1
if token not in OPERATORS:
return int(token)
right = helper() # the right operand comes first when reading backward
left = helper()
return self._apply(token, left, right)
return helper()
def _apply(self, op: str, a: int, b: int) -> int:
if op == "+":
return a + b
if op == "-":
return a - b
if op == "*":
return a * b
q = abs(a) // abs(b) # truncate toward zero
return q if (a < 0) == (b < 0) else -q
if __name__ == "__main__":
print(Solution().evalRPN(["2", "1", "+", "3", "*"]))
print(Solution().evalRPN(["4", "13", "5", "/", "+"]))
print(Solution().evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))RecapThe whole problem in a few lines, for the night before
- Spot it: a postfix expression where operators come after their numbers
- Idea: use a stack; push numbers, and on an operator pop two values, apply it, and push the result
- Cost: O(n) time, O(n) space
- Trap: the first value popped is the right operand, which matters for
-and/; division truncates toward zero, so Python's//is wrong for negatives
Interview follow-ups
What if the expression can also include a unary minus that negates a whole sub-expression?
RPN cannot tell a unary minus from a binary one by looking at a single
-token. So give the unary operator its own token, for example"~"for "negate the value before it". A unary operator pops only one value, negates it and pushes the result back. Everything else about the stack walk stays the same, and the time stays O(n).The expression is generated dynamically and could be malformed. How would you make this robust?
Check at each step instead of assuming the input is valid. Before popping for an operator, confirm the stack holds at least two values. After the last token, confirm exactly one value is left. Either check failing means the expression is malformed, and you raise a clear error with the token position, rather than letting a plain
pop()on an empty stack throw a confusing low-level exception. Division by zero needs its own check.
Frequently asked questions
+ and * are commutative: a + b always equals b + a, so it does not matter which popped value you call a. Subtraction and division are not: a - b and b - a are different. The stack approach treats the value popped second (pushed earlier, so it appeared first in the expression) as the left operand. If you get that backwards, every expression with a - or / comes out wrong, even though +-only and *-only expressions still look right.
// in Python rounds down, toward negative infinity. So -13 // 5 gives -3, but the problem wants truncation toward zero, which is -2. The two only agree when both operands have the same sign. The Python code divides the absolute values and then fixes the sign. Java and C++ integer division already truncates toward zero, so they need no extra step.
Postfix is the shape a lot of "compiled" expressions end up in: a metrics query's filter, a load balancer's routing rule, or a build tool's dependency expression. Reducing them to postfix makes runtime evaluation a simple, predictable, single-pass stack walk, with no parser for operator precedence.
Not in cost: both are O(n) time and O(n) space, and the stack version avoids the recursion-depth risk on very long chains. It is still worth knowing, because "solve it without an explicit data structure" is a common follow-up. Seeing that the call stack can stand in for an explicit one is a useful skill for many divide-and-conquer problems.
