Evaluate Reverse Polish Notation
Medium· stack· expression evaluation
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
Input: tokens = ["2","1","+","3","*"]
Output: 9
(2 + 1) * 3.
Input: tokens = ["4","13","5","/","+"]
Output: 6
4 + (13 / 5) = 4 + 2.
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)