Evaluate Reverse Polish Notation: Stack evaluation Pattern

Learning Outcome

After this lesson, you should be able to evaluate postfix expressions by storing operands until an operator is ready to apply.

Problem Statement

Given an array of tokens in Reverse Polish Notation, evaluate the expression and return the integer result. Operators are applied to the two most recent operands.

Brute Force Approach

Repeatedly search the token list for an operator, apply it to the two previous numbers, replace the three tokens with the result, and continue.

This works conceptually, but repeated list edits are inefficient and awkward.

Optimized Approach

Use a stack. Push numbers. When an operator appears, pop the right operand first, then the left operand, apply the operator, and push the result back.

The operand order matters for subtraction and division.

Exact Pseudocode

stack = empty stack
for token in tokens:
  if token is a number:
    push integer(token)
  else:
    right = pop stack
    left = pop stack
    result = apply token to left and right
    push result
return stack.top
  

Reference Code

class Solution:
    def evalRPN(self, tokens):
        stack = []

        for token in tokens:
            if token not in {"+", "-", "*", "/"}:
                stack.append(int(token))
                continue

            right = stack.pop()
            left = stack.pop()

            if token == "+":
                stack.append(left + right)
            elif token == "-":
                stack.append(left - right)
            elif token == "*":
                stack.append(left * right)
            else:
                stack.append(int(left / right))

        return stack[-1]
  

Sample Dry Run

Complexity

Edge Cases

• Negative number tokens such as "-11".
• Subtraction and division require correct operand order.
• Integer division truncates toward zero in the common problem definition.

Interview Checklist

• Pop right operand first, then left operand.
• Distinguish negative numbers from the minus operator.
• Use truncation toward zero for division.

FAQs