Evaluate Reverse Polish Notation
Part of Practice: Classic Stacks
Evaluate an arithmetic expression written in Reverse Polish Notation (RPN, also called postfix): the operator comes after its two operands, so "3 4 +" means 3 + 4. You are given the expression as an array of token strings, each either an integer (possibly negative) or one of +, -, *, /.
Division between integers truncates toward zero (so 6/-132 is 0, and -7/2 is -3, not -4). The input is guaranteed to be a valid RPN expression, all intermediate values fit in a 32-bit integer, and there is no division by zero.
Examples
- Input:
- tokens = ["2","1","+","3","*"]
- Output:
- 9
Reads as (2 + 1) * 3. The "+" consumes 2 and 1 producing 3; the "*" consumes that 3 and the token 3.
- Input:
- tokens = ["4","13","5","/","+"]
- Output:
- 6
Reads as 4 + (13 / 5). Integer division truncates 2.6 down to 2, then 4 + 2 = 6.
- Input:
- tokens = ["18","6","3","/","-"]
- Output:
- 16
The "/" pops 3 then 6 and must compute 6 / 3 = 2 (second-popped ÷ first-popped), then 18 - 2 = 16. Getting the operand order backwards gives 18 - 0 instead.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.