Evaluate Reverse Polish Notation
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Evaluate an arithmetic expression written in postfix form, where each operator comes after its two operands. Tokens are integers or one of + - * /, and division truncates toward zero. The expression is always valid.
Examples
Constraints
- • 1 <= tokens.length <= 10^4
- • Values fit in a 32-bit integer
Hints & approach
Hint 1
Numbers wait until an operator needs them.
Hint 2
An operator always uses the two most recent pending values.
Hint 3
Watch the operand order for - and /.
Approachtry the hints first
Scan tokens with a stack. Push numbers. On an operator, pop b then a (b was pushed last), compute a op b, and push the result. Truncate division toward zero explicitly in languages where integer division floors. At the end the single remaining value is the answer.
Time O(n) · Space O(n)
