449. Postfix Evaluator
An old cash register stores every price calculation in postfix order, with no brackets at all: the two operands of an operator always come just before it, so ["3", "4", "+"] stands for 3 + 4. Each token is text. It is either an operator (+, -, * or /) or a whole number that may carry a leading minus sign.
Evaluate the list tokens from left to right and return the final value. Integer division discards the fractional part and rounds toward zero, so -7 divided by 2 gives -3. The list is always a valid postfix expression, a division by zero never occurs, and every operand, intermediate value and the final result fits in a signed 32-bit integer.
Example 1
- Input:
- tokens = ["6","4","+","3","-","8","2","/","*"]
- Output:
- 28
- Explanation:
6 + 4 = 10 and 10 - 3 = 7. Separately 8 / 2 = 4. The final multiplication gives 7 * 4 = 28.
Example 2
- Input:
- tokens = ["-17","5","/","3","-","9","+"]
- Output:
- 3
- Explanation:
-17 / 5 is -3.4 which rounds toward zero to -3. Then -3 - 3 = -6 and -6 + 9 = 3.
Constraints
1 ≤ tokens.length ≤ 8000
Each token is +, -, *, / or an integer in [-231, 231 - 1]
The expression is valid and never divides by zero.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)