Frontend Beauty
ESC

Type to search the knowledge base.

Evaluate Reverse Polish Notation

Evaluate RPN with a stack — operands push, operators pop-two apply, integer division toward zero in JS.

intermediate3 min read
  • dsa
  • stack
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Evaluate an arithmetic expression in Reverse Polish Notation (postfix). Valid operators: + - * /. Division truncates toward zero. Tokens are integers or operators.

["2","1","+","3","*"] → ((2+1)*3) = 9
["4","13","5","/","+"] → (4+(13/5)) = 6
["10","6","9","3","+","-11","*","/","*","17","+","5","+"] → 22

Why a stack?

Postfix removes parentheses: when you see an operator, its operands are the two most recent values.

Brute: convert to infix then eval

Shunting-yard reverse + eval — overkill and unsafe. Don’t.

Optimal: stack of numbers

function evalRPN(tokens: string[]): number {
  const st: number[] = [];

  for (const tok of tokens) {
    if (tok === "+" || tok === "-" || tok === "*" || tok === "/") {
      const b = st.pop()!;
      const a = st.pop()!;
      let v: number;
      if (tok === "+") v = a + b;
      else if (tok === "-") v = a - b;
      else if (tok === "*") v = a * b;
      else v = truncDiv(a, b);
      st.push(v);
    } else {
      st.push(Number(tok));
    }
  }
  return st[0];
}

/** Division toward zero (JS Math.trunc) */
function truncDiv(a: number, b: number): number {
  return Math.trunc(a / b);
}
Time O(n)
Space O(n)

JS footgun: Math.floor vs toward zero

Math.floor(-7 / 2) = -4, but toward zero is -3. Use Math.trunc (or bitwise hacks carefully — prefer trunc).

Math.trunc(-7 / 2); // -3  ✓ for RPN LC
Math.floor(-7 / 2); // -4  ✗

Operand order

Pop b then a — expression is a op b. Reversing breaks subtraction/division.

Walk ["4","13","5","/","+"]

token stack
4 [4]
13 [4,13]
5 [4,13,5]
/ [4, 2] // 13/5 trunc
+ [6]

Edge cases

  • Single number token
  • Negatives in tokens ("-11") — Number(tok) works; don’t treat leading - as operator without care
  • Division results
  • Constraints guarantee valid RPN

Common mistakes

  • Floor division for negatives
  • Wrong pop order
  • Using eval on joined string

Interview delivery

  1. Stack machine explanation.
  2. Code ops carefully.
  3. Call out trunc division.
  4. Trace one example.
  5. O(n).

Mental model

RPN is how compilers and some calculators avoid precedence parsers: operators always apply to the top of the stack. Your job is a stack machine, not string rewriting.

Operator map style

const op: Record<string, (a: number, b: number) => number> = {
  '+': (a, b) => a + b,
  '-': (a, b) => a - b,
  '*': (a, b) => a * b,
  '/': (a, b) => Math.trunc(a / b),
};

Keeps the loop clean. Still pop b then a.

Out-loud answer

“Scan tokens; numbers push; operators pop two, apply, push. Division truncates toward zero — Math.trunc in JS, not floor. O(n) time and space. Valid RPN guaranteed.”

Further reading