Reverse Polish Notation

Tags

Reverse Polish Notation

Category

Stacks

Difficulty

Medium

Problem Statement

Evaluate an arithmetic expression given in Reverse Polish Notation (postfix notation). The expression is provided as an array of strings where each element is either an integer or an operator (+, -, *, /). Division should truncate toward zero.

Intuition

In RPN, operands come before their operators. A stack naturally models this: we push operands, and when we encounter an operator, we pop the two most recent operands, apply the operation, and push the result back. The final value on the stack is the answer.

Approach

  1. Initialize an empty stack.
  2. Iterate through each token in the input array: a. If the token is a number, push it onto the stack. b. If the token is an operator (+, -, *, /):
    • Pop the top two values from the stack. The first popped value is the right operand, the second is the left operand.
    • Apply the operator: left op right.
    • For division, truncate toward zero (not floor division).
    • Push the result back onto the stack.
  3. The single remaining value on the stack is the final result.

Pseudocode

function evalRPN(tokens):
    stack = []
    operators = {"+", "-", "*", "/"}

    for token in tokens:
        if token in operators:
            right = stack.pop()
            left = stack.pop()
            if token == "+": result = left + right
            elif token == "-": result = left - right
            elif token == "*": result = left * right
            elif token == "/": result = truncate(left / right)
            stack.push(result)
        else:
            stack.push(int(token))

    return stack.pop()

Time & Space Complexity

  • Time: O(n) where n is the number of tokens. Each token is processed exactly once.
  • Space: O(n) for the stack, which in the worst case holds all operands before any operator is encountered.

Key Insights

  • The order of popping matters: the first popped value is the right operand, the second is the left operand. This is critical for non-commutative operations (subtraction and division).
  • Division truncation toward zero differs from floor division for negative numbers. For example, -7 / 2 = -3 (truncate) vs -4 (floor).
  • A valid RPN expression always has exactly one value remaining on the stack at the end.
  • RPN eliminates the need for parentheses and operator precedence rules.

Edge Cases

  • Single token (just a number): return that number directly.
  • Negative numbers in the input: tokens like "-5" should be parsed as the integer -5, not as the minus operator.
  • Division by large numbers resulting in zero after truncation.
  • Large intermediate results: depending on the language, may need to handle overflow.
  • Expression with only one operator and two operands: simplest non-trivial case.

Linked mentions