Evaluate Reverse Polish Notation

Difficulty: Medium

You're given an arithmetic expression written in postfix notation (also called Reverse Polish Notation), as a list of tokens. In postfix notation, each operator comes right after the two numbers it applies to, instead of sitting between them — so 3 4 + means "3 plus 4", and there's never any need for parentheses.

Evaluate the expression and return its value. The only operators you'll see are +, -, *, and /, and division should truncate toward zero (so 13 / 5 is 2, not 2.6 or 3).

Examples

Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9

Reading left to right: 2 and 1 combine with + to make 3, then that 3 and the next 3 combine with * to make 9 — this is the postfix form of (2 + 1) * 3.

Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6

13 / 5 truncates to 2, then 4 + 2 = 6.

Input: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22

Constraints

1 <= tokens.length <= 10^4
Each token is either an operator (+, -, *, /) or an integer.
Division always truncates toward zero, and the input never divides by zero.

Approach

Postfix notation exists precisely because it can be evaluated with a single left-to-right pass and a stack, with no need to think about operator precedence or parentheses at all.

Walk through the tokens one at a time. Whenever you see a number, push it onto the stack. Whenever you see an operator, pop the top two numbers off — the second-to-last one popped is the left-hand operand, the last one popped is the right-hand operand — apply the operator, and push the result back onto the stack. By the time you reach the end of the tokens, exactly one number is left on the stack: the answer.

Solutions

Brute Force — Repeatedly Collapse the First Operator Found

Simulate the evaluation directly on a copy of the token list: repeatedly scan for the first operator, apply it to the two numbers right before it, splice the result back into the list, and repeat until only one token remains.

function evalRPN(tokens) {
  const ops = new Set(["+", "-", "*", "/"]);
  const arr = [...tokens];

  while (arr.length > 1) {
    const opIndex = arr.findIndex((t) => ops.has(t));
    const b = Number(arr[opIndex - 1]);
    const a = Number(arr[opIndex - 2]);
    let result;
    switch (arr[opIndex]) {
      case "+": result = a + b; break;
      case "-": result = a - b; break;
      case "*": result = a * b; break;
      case "/": result = Math.trunc(a / b); break;
    }
    arr.splice(opIndex - 2, 3, String(result));
  }

  return Number(arr[0]);
}

Time: O(n²), since each pass re-scans and splices the array · Space: O(n)

Optimal — Stack

Push numbers onto a stack as they appear. When an operator appears, pop the top two numbers (in the right order), apply the operator, and push the result. One pass through the tokens, and no re-scanning.

function evalRPN(tokens) {
  const stack = [];

  for (const token of tokens) {
    if (token === "+" || token === "-" || token === "*" || token === "/") {
      const b = stack.pop();
      const a = stack.pop();
      let result;
      switch (token) {
        case "+": result = a + b; break;
        case "-": result = a - b; break;
        case "*": result = a * b; break;
        case "/": result = Math.trunc(a / b); break;
      }
      stack.push(result);
    } else {
      stack.push(Number(token));
    }
  }

  return stack.pop();
}

Time: O(n) · Space: O(n)