Given an expression in reverse Polish notation as a list of tokens, with the operators +, -, * and /, return its value. Division truncates toward zero.
Before you code
In postfix notation, every operator applies to the two most recent values. That is a stack: push numbers, and let each operator pop its operands and push its result.
Hints
- Pop the right operand first, then the left: for
a b -, the result isa − b, notb − a. - Truncate toward zero: in Python,
int(a / b), nota // b, which rounds toward negative infinity (-7 // 2is -4, but the answer is -3). - At the end, the stack holds exactly one value: the answer.
Production & complexity notes
When solving Evaluate reverse Polish notation on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Stacks and the LIFO rule to reinforce the underlying pattern.
What it practices
The operand stack that calculators and virtual machines use, from Stacks and the LIFO rule.