You are given an arithmetic expression in Reverse Polish Notation (postfix) as an array of string tokens. Each token is an integer or one of the operators +, -, * and /. Evaluate the expression and return the result as an integer. Division truncates toward zero, there is never a division by zero, and the expression is always valid.
(2 + 1) * 3 = 94 + (13 / 5) = 4 + 2 = 6- 1 <= tokens.length <= 10^4
- Each token is an operator or an integer in [-200, 200]
- Every intermediate result fits in a 32-bit integer
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force could repeatedly scan the array for the first operator, combine the two numbers before it and rebuild the array, which is O(n^2). Postfix notation was designed for a stack: reading left to right, every operator works on the two latest operands. Push numbers, and when an operator arrives pop two values, apply it and push the result back. One pass is enough.
Algorithm
- Create an empty stack.
- For each token: if it is a number, push it.
- If it is an operator, pop
b(right operand) and thena(left operand). - Push
a op b, using division that truncates toward zero. - Return the single value left on the stack.
O(n)Space: O(n)// floors (-7 // 2 == -4), so use int(a / b) or handle signs yourself to truncate toward zero like Java and C++.class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] for t in tokens: if t in ('+', '-', '*', '/'): b = stack.pop() # right operand comes off first a = stack.pop() if t == '+': stack.append(a + b) elif t == '-': stack.append(a - b) elif t == '*': stack.append(a * b) else: # truncate toward zero (Python's // would floor) q = abs(a) // abs(b) stack.append(q if (a >= 0) == (b >= 0) else -q) else: stack.append(int(t)) return stack[-1]