Evaluate reverse Polish notation

Medium TimeO(n) SpaceO(n)

In reverse Polish notation each operator comes after its two operands, so ["2", "1", "+", "3", "*"] means (2 + 1) × 3 and needs no brackets or precedence rules at all. Given a well-formed expression tokens, return its value. Every operator takes the two values immediately before it, and division truncates towards zero.

Examples

Example 1

Input
tokens = ["2", "1", "+", "3", "*"]
Output
9
2 + 1 = 3, and then 3 × 3 = 9.

Example 2

Input
tokens = ["-7", "2", "/"]
Output
-3
-7 ÷ 2 is -3.5, and truncating towards zero gives -3 rather than -4.

The Code

function evalRPN(tokens) {
  const stack = [];
  for (let i = 0; i < tokens.length; i++) {
    const t = tokens[i];
    if (t === "+" || t === "-" || t === "*" || t === "/") {
      const b = stack.pop();
      const a = stack.pop();
      if (t === "+") stack.push(a + b);
      else if (t === "-") stack.push(a - b);
      else if (t === "*") stack.push(a * b);
      else stack.push(Math.trunc(a / b));
    } else {
      stack.push(Number(t));
    }
  }
  return stack.pop();
}
evalRPN(["2", "1", "+", "3", "*"]);
Done
Step through evalRPN(["2", "1", "+", "3", "*"]) call by call

More like this

All stacks & queues examples (8) →