150. Evaluate Reverse Polish Notation
You are given tokens, the pieces of an arithmetic expression written in reverse Polish (postfix) notation: each token is either an integer or one of the four operators +, -, *, /. Evaluate the expression and return its value as a single integer.
In postfix notation an operator applies to the two values produced just before it, so 3 4 + means 3 + 4 and 5 1 2 + 4 * + 3 - means 5 + ((1 + 2) * 4) - 3. The rules:
- Every operator takes exactly two operands.
- Division between integers truncates toward zero:
13 / 5 = 2and-13 / 5 = -2. - The expression is always valid, there is no division by zero, and every intermediate value fits in a 32-bit signed integer.
Example 1:
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: `2 1 +` collapses to 3, leaving `3 3 *`, which is 9. In infix: (2 + 1) * 3.
Example 2:
Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Explanation: `13 5 /` truncates to 2, leaving `4 2 +` = 6. In infix: 4 + (13 / 5).
Constraints:
- 1 ≤ number of tokens ≤ 10⁴
- Each token is `+`, `-`, `*`, `/`, or an integer in [-200, 200]
- The expression is valid postfix and never divides by zero
- Every intermediate value fits in a 32-bit signed integer
Hints:
Read the tokens left to right. When you meet a number you cannot do anything with it yet — you have to remember it. When you meet an operator, it needs exactly the *two most recently remembered* values. Which data structure hands back the most recent thing first?
Push numbers onto a stack; on an operator, pop `b` then `a` (order matters for `-` and `/`!), push `a op b`. For division, make sure your language truncates toward zero — Python's `//` floors instead, so compute `abs(a) // abs(b)` and reapply the sign.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: tokens = ["2", "1", "+", "3", "*"]
Expected output: 9