LeetEye LeetEye
Medium Stack ~5 min

Evaluate Reverse Polish Notation

stack evaluate-reverse-polish-notation

Problem

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (RPN).

Evaluate the expression and return an integer representing the value.

Notes:
- Valid operators are +, -, *, and /
- Each operand may be an integer or another expression
- Division truncates toward zero
- No division by zero
- Answer fits in 32-bit integer

Examples

Example 1
Input: tokens = ["2","1","+","3","*"]
Output: 9
((2 + 1) * 3) = 9
Example 2
Input: tokens = ["4","13","5","/","+"]
Output: 6
(4 + (13 / 5)) = 4 + 2 = 6
Example 3
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Key Insight

When you see an operator, apply it to the two most recent numbers.

RPN evaluation: numbers go on stack, operators pop two, compute, push result. Final answer is stack's only element.

How to Approach This Problem

Pattern Recognition: When you see keywords like evaluate reverse polish notation stack, think Stack.

Step-by-Step Reasoning

1 When you encounter a number token, you should:
Answer: Push it onto the stack
Numbers wait on the stack until an operator needs them.
2 When you encounter an operator, you should:
Answer: Pop two operands, apply operator, push result
Binary operators need two operands. Result goes back on stack for future operations.
3 For tokens ["10", "3", "-"], the result is:
Answer: 10 - 3 = 7
First number pushed (10) is second popped. Order is: second_popped OP first_popped = 10 - 3 = 7.
4 If stack is [10, 3] and operator is "/": Pop 3, pop 10. The computation is:
Answer: 10 / 3
The operand pushed first (10) is the dividend. Operand pushed second (3) is the divisor. 10 / 3 = 3 (truncated).
5 After processing all tokens, the answer is:
Answer: The top (and only) element of the stack
Valid RPN expression reduces to exactly one value on the stack.

Solution

def evalRPN(tokens: List[str]) -> int:
    stack = []
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token in operators:
            b = stack.pop()  # Second operand
            a = stack.pop()  # First operand
            
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:  # Division truncates toward zero
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    
    return stack[0]

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Stack problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye