Evaluate Reverse Polish Notation
Task example: Evaluate Reverse Polish Notation
Read an expression whose operators follow their operands. Evaluate the tokens and return one integer. Use +, -, *, and /. Division truncates toward zero. The given expression is valid, division by zero does not occur, and all intermediate results fit in a signed 32-bit integer.
tokens = ["2", "1", "+", "3", "*"] → 9
First combine 2 + 1 = 3, then 3 * 3 = 9. Operands may themselves be the results of earlier operations.
Source task: LeetCode 150Repeated reduction: video explanation
tokens = ["2", "1", "+", "3", "*"] → 9
Prefer reading? Follow the steps below.
- Copy the tokens. Find the first operator: the two tokens directly before it are numbers ready to combine. Read the left number as a and the right number as b.
- Compute a + b, a - b, a * b, or int(a / b). Replace those three tokens with the result and restart the scan. For the task’s 32-bit values, int(a / b) correctly truncates toward zero.
- Stop when only one token remains and return it as an integer. A single-number input needs no reductions. The original input stays unchanged.
Time complexity · O(n²)
With n tokens, up to O(n) reductions each scan or shift O(n) list entries. The worst-case total is O(n²).
Space complexity · O(n)
The working copy holds O(n) tokens. Only a constant number of operands and result variables are needed beyond that copy.
Stack evaluation: video explanation
tokens = ["2", "1", "+", "3", "*"] → 9
Prefer reading? Follow the steps below.
- Scan left to right. Push each number onto the stack. It stores completed partial results that have not yet been combined.
- At an operator, pop b first, then a. Calculate a operator b and push the result. Reversing the operands breaks subtraction and division.
- After all tokens, return the only stack value. For -7 / 3, use int(-7 / 3) = -2. Python -7 // 3 is -3 because floor division rounds down.
The stack reduces worst-case time from O(n²) to O(n) by avoiding repeated scans and list shifts. Both approaches use O(n) space.
Time complexity · O(n)
Each token is read once. Each partial result is pushed once and popped at most once. Python list append and end-pop are amortized O(1), giving O(n) total time.
Space complexity · O(n)
The stack may hold O(n) numbers when many operands appear before their operators. No copy of the input is required.