You are given tokens, an arithmetic expression in reverse Polish (postfix) notation: each
operator comes after the two values it works on. So ["4", "2", "-"] means 4 − 2, and
["1", "2", "+", "5", "*"] means (1 + 2) × 5. No brackets are ever needed.
Each token is either an integer, written in decimal (perhaps with a leading -), or one of the
operators +, -, * and /. Return the value of the expression.
Division keeps only the whole-number part, rounding towards zero: 7 / 2 is 3 and −7 / 2 is −3. The expression is always valid, never divides by zero, and every value along the way fits in a 32-bit signed integer.
Example 1
- Input
- tokens = ["2", "3", "4", "*", "+", "10", "5", "-", "/"]
- Output
- 2
Example 2
- Input
- tokens = ["9", "-4", "/"]
- Output
- -2
Constraints
tokensholds 1 to 10⁴ tokens.- Every number in
tokensis between −200 and 200. - Every intermediate result is between −2³¹ and 2³¹ − 1.
Show the pattern
Stack
In postfix notation an operator always works on the two most recent values that haven't been used yet. "Most recent first" is exactly what a stack gives you.
See stack in a visualiserShow the approach
Scan the tokens with a stack of values. A number is pushed. An operator pops two values (the first one popped is the right operand), combines them, and pushes the result. When the tokens run out, the stack holds a single value: the answer.
Each token is pushed or popped a constant number of times, so one pass does it.
Time: O(n) · Space: O(n)