visual walkthrough
Evaluate Reverse Polish Notation
Stack-based expression evaluation, the basis of calculators.
The idea
In Reverse Polish Notation an operator always applies to the two most recent results. A stack keeps exactly those: numbers are pushed, and an operator pops two, computes, and pushes the answer.
Pop order matters for − and ÷: the first pop is the right operand.
Complexity
| approach | time | space |
|---|---|---|
| Reduce the list | O(n²) | O(n) |
| Stack | O(n) | O(n) |