25. Evaluate Reverse Polish Notation

MediumArray Stack Math

An arithmetic expression is written in Reverse Polish Notation (postfix): every operator comes after its two operands, so no parentheses are ever needed. For example, (1 + 2) * 3 is written as 1 2 + 3 *.

You are given the expression as an array of string tokens tokens. Each token is either an integer or one of the operators +, -, *, /. Evaluate the expression and return its value as an integer.

For - and /, the operand that appeared first is on the left: ["8","2","-"] means 8 - 2.
Division between two integers truncates toward zero (so 7 / -2 is -3, not -4).
The expression is always valid and never divides by zero.

Example 1

Input: tokens = ["3","4","+","2","*"]
Output: 14

Explanation: (3 + 4) * 2 = 14.

Example 2

Input: tokens = ["7","-3","/"]
Output: -2

Explanation: 7 / -3 is about -2.33, which truncates toward zero to -2.

Example 3

Input: tokens = ["2","10","5","/","+","6","*"]
Output: 24

Explanation: (2 + 10 / 5) * 6 = (2 + 2) * 6 = 24.

Constraints

1 <= tokens.length <= 10^4
Each token is "+", "-", "*", "/" or an integer in the range [-1000, 1000]
The expression 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