Stack · 061Medium
Evaluate Reverse Polish Notation
Evaluate an arithmetic expression given in Reverse Polish Notation as an array of tokens. Valid operators are +, -, *, /. Division truncates toward zero.
Constraints
- 1 <= tokens.length <= 10^4
- Each token is an operator or an integer in [-200, 200].
- The expression is always valid and never divides by zero.
Examples
evalRPN(["2", "1", "+", "3", "*"]) -> 9 // ((2 + 1) * 3) evalRPN(["4", "13", "5", "/", "+"]) -> 6 // (4 + (13 / 5)) evalRPN(["-7", "2", "/"]) -> -3 // truncates toward zero, not -4 evalRPN(["5"]) -> 5 // a lone operand evalRPN(["3", "4", "-"]) -> -1 // left operand is the second pop: 3 - 4 evalRPN(["4", "-2", "/", "2", "-"]) -> -4 // negative token, then (4 / -2) - 2
Edge cases
- Division truncates toward ZERO — use Math.trunc, not Math.floor.
- Operand order matters: the second pop is the left operand for - and /.
- Negative number tokens are valid input, not operators.
Show the target complexity (spoiler)
- Naive
- There is no meaningfully worse approach — a single stack pass is the natural
- Target
- O(n) time, O(n) space — push numbers, and on an operator pop two, apply, and push the result.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/04-stack/061-evaluate-reverse-polish-notation.js ./practice c 061