Evaluate Reverse Polish Notation
On this page
Problem statement
Evaluate an arithmetic expression written in Reverse Polish Notation (postfix) and return its integer value. The input is a list of tokens: integers (possibly negative) and the operators
+,-,*,/. Each operator applies to the two values produced just before it. Division truncates toward zero. The expression is always valid and never divides by zero.
A short stack question that checks whether you know why postfix needs no parentheses, and whether you get the operand order and integer division right. Original problem: LeetCode 150.
Example

Input: ["3", "4", "+", "2", "*", "7", "-"]
Output: 7 # (3 + 4) * 2 - 7
Input: ["15", "7", "1", "1", "+", "-", "/", "3", "*"] -> 9 # 15 / (7 - (1 + 1)) * 3
Input: ["7", "-2", "/"] -> -3 # truncate toward zero
Constraints (assumed)
- 1 ≤ number of tokens ≤ 10⁴; every intermediate value fits in 32 bits.
What this question tests
- Recognizing that postfix evaluation is a stack problem.
- Popping operands in the right order for
-and/. - Language details: truncating division and parsing negative numbers.
Questions to ask first
- How does division round? (Here: toward zero, so 7 / −2 = −3.)
- Can numbers be negative? (Here: yes;
"-2"is a number,"-"is an operator.) - Is the input always valid? (Here: yes. Validation is a follow-up.)
- Which operators? (Here: the four basic ones.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.