Evaluate Reverse Polish Notation

MediumArray Stack Math

A spreadsheet engine compiles every formula into Reverse Polish Notation (postfix) before evaluating it. In postfix, each operator comes right after the two values it combines, so parentheses are never needed: the formula (5 - 1) * 3 compiles to 5 1 - 3 *.

You receive a compiled formula as an array of strings tokens. Each token is either an integer or one of the operators +, -, * and /. Evaluate the formula and return the result.

An operator combines the two most recent values that have not been used yet, and the older of the two is the left operand: ["9","4","-"] means 9 - 4.
Integer division rounds toward zero, so -7 / 2 is -3.
Every formula is well-formed and never divides by zero.

Example 1

Input: tokens = ["8","3","*","4","-"]
Output: 20

Explanation: The formula is 8 * 3 - 4 = 20.

Example 2

Input: tokens = ["-9","4","/"]
Output: -2

Explanation: -9 / 4 is -2.25, and rounding toward zero gives -2.

Example 3

Input: tokens = ["15","7","1","1","+","-","/","3","*"]
Output: 9

Explanation: The formula is 15 / (7 - (1 + 1)) * 3 = 15 / 5 * 3 = 9.

Constraints

tokens contains between 1 and 10^4 tokens.
Every number token is an integer from -1000 to 1000; every other token is one of +, -, *, /.
The formula is valid, and every intermediate result fits in a 32-bit signed integer.

💡 Hint 1

Scan left to right. Numbers wait around until an operator needs them; which structure hands back the most recent ones first?

💡 Hint 2

On an operator, pop two values. The first one you pop is the right operand.

💡 Hint 3

Watch the rounding of division: JavaScript needs Math.trunc, Java's / on ints already truncates toward zero.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Postfix notation is made for a stack. Walk the tokens in order: push every number; on an operator, pop the right operand b, then the left operand a, and push a op b. Because the expression is valid, exactly one value remains at the end, and that is the answer. The only subtlety is division, which must truncate toward zero: use Math.trunc(a / b) in JavaScript, while Java's integer / already behaves that way.

Time O(n)Space O(n)

function evalRPN(tokens) {
  const stack = [];
  for (const t of tokens) {
    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();
}

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String t : tokens) {
            switch (t) {
                case "+": stack.push(stack.pop() + stack.pop()); break;
                case "*": stack.push(stack.pop() * stack.pop()); break;
                case "-": { int b = stack.pop(), a = stack.pop(); stack.push(a - b); break; }
                case "/": { int b = stack.pop(), a = stack.pop(); stack.push(a / b); break; }
                default: stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}

/**
 * @param {string[]} tokens
 * @return {number}
 */
function evalRPN(tokens) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit