Evaluate Reverse Polish Notation
MediumStack
You are given a list of strings tokens that forms an arithmetic expression in Reverse Polish Notation (postfix notation). In this notation an operator comes after its two operands: ["3", "4", "+"] means 3 + 4, and ["5", "1", "2", "+", "*"] means 5 * (1 + 2).
Each token is either an integer (possibly negative, like "-7") or one of the operators +, -, *, /. For an operator, the operand that appeared earlier is the left operand: ["a", "b", "-"] means a - b.
Integer division truncates toward zero (so -7 / 2 is -3, not -4).
Return the integer value of the expression.
Example 1
- Input:
- tokens = ["10", "4", "3", "+", "2", "*", "-"]
- Output:
- -4
- Explanation
4 3 +gives 7, then7 2 *gives 14, and finally10 14 -gives 10 - 14 = -4. The earlier operand (10) is on the left of the subtraction.
Example 2
- Input:
- tokens = ["-7", "3", "/"]
- Output:
- -2
- Explanation
- -7 / 3 is -2.33..., and truncating toward zero gives -2 (not -3, which floor division would give).
Example 3
- Input:
- tokens = ["42"]
- Output:
- 42
- Explanation
- A single number is already a complete expression.
Constraints
- 1 ≤
tokens.length≤ 104 - Each token is an operator (
+,-,*,/) or an integer in the range [-200, 200] - The expression is always valid and never divides by zero
- The result and every intermediate value fit in a 32-bit signed integer