The problem
In reverse Polish notation an operator comes after its two operands: 2 1 + 3 * means (2 + 1) × 3. Given such an expression as a list of tokens, return its value.
The operators are +, −, × (written *) and /. Division between integers truncates toward zero, so 7 / −2 is −3. The expression is always valid.
Examples
01
- Input
tokens = ["2", "1", "+", "3", "*"]
- Output
9
02
- Input
tokens = ["4", "13", "5", "/", "+"]
- Output
6
03
- Input
tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
- Output
22
Constraints
- 1 ≤ tokens.length ≤ 10⁴
- Each token is an operator or an integer in [−200, 200].
- Every intermediate result fits in 32 bits.
The idea
Read the tokens left to right. A number waits on a stack until an operator needs it. An operator takes the top two numbers — the top one is its right operand, the one beneath its left — and pushes the result back.
When the tokens run out, the one number left on the stack is the value of the whole expression.
- Time
- O(n)
- Space
- O(n) — the stack
Solution · every language run against every case
class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] for tok in tokens: if tok in "+-*/": b, a = stack.pop(), stack.pop() # the right operand is on top if tok == "+": stack.append(a + b) elif tok == "-": stack.append(a - b) elif tok == "*": stack.append(a * b) else: stack.append(int(a / b)) # division truncates toward zero else: stack.append(int(tok)) return stack[0]