Evaluate Reverse Polish Notation

MediumStackArrayMathStack

Problem

You are given an arithmetic expression written in Reverse Polish, or postfix, notation as a list of tokens, where each token is either a number or an operator, and operators come after the two values they act on rather than between them. Evaluate the expression and return its integer result.

Example. The tokens 2, 1, +, 3, * mean add 2 and 1, then multiply the result by 3, which evaluates to 9.

Key idea

Ordinary infix expressions need parentheses and precedence rules to know which operation to apply first, which makes direct left-to-right evaluation unreliable. Postfix notation sidesteps that entirely: by the time an operator appears, both of its operands have already appeared and are fully resolved, so there is never any ambiguity about order.

This makes a stack the natural tool. Scan the tokens left to right, pushing each number onto the stack. When a token is an operator, pop the two most recently pushed values, apply the operator to them, and push the result back. Because postfix guarantees every operator's operands were pushed immediately before it, the top two stack entries are always exactly the values that operator needs. After the last token, the single value remaining on the stack is the answer.

Solution

function evalRPN(tokens: string[]): number {
  const operators = new Set(['+', '-', '*', '/']);
  const stack: number[] = [];

  for (const token of tokens) {
    if (operators.has(token)) {
      // Operand order matters: the value popped first was pushed most recently.
      const right = stack.pop()!;
      const left = stack.pop()!;
      switch (token) {
        case '+':
          stack.push(left + right);
          break;
        case '-':
          stack.push(left - right);
          break;
        case '*':
          stack.push(left * right);
          break;
        case '/':
          // Truncate toward zero rather than floor.
          stack.push(Math.trunc(left / right));
          break;
      }
    } else {
      stack.push(Number(token));
    }
  }

  // The single value left on the stack is the fully reduced result.
  return stack.pop()!;
}

Complexity

  • Time: O(n). Each token is processed once with constant-time stack operations.
  • Space: O(n). The stack holds intermediate operands, up to the length of the token list in the worst case.

Watch out for

  • Order matters for subtraction and division: the value popped second is the left-hand operand, and the value popped first is the right-hand operand.
  • Integer division should truncate toward zero if the problem requires it, which differs from some languages' default flooring behavior.
  • Distinguish a minus sign that starts a negative number token from a minus operator token during parsing.

Pattern

This is stack-based evaluation of postfix expressions, a core technique in expression parsing and calculator implementations, closely related to converting infix expressions into postfix form and to evaluating expression trees.

Related questions