Evaluate Reverse Polish Notation

The problem

The list tokens is an arithmetic expression in reverse Polish notation: each operator comes after the two values it applies to, not between them. So "3 5 -" means 3 minus 5, and "2 1 + 3 *" means (2 + 1) × 3, because a value can be the result of an earlier operator. Each token is an integer written as a string, possibly negative, or one of the operators +, -, * and /. Division drops any fraction, so -7 / 3 gives -2. The expression is always valid and never divides by zero. Return its value as a number.

What to write

function solve(tokens: string[]): number

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

Output
9

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

Output
6

Constraints

1–1,000 valid postfix tokens; signed 32-bit intermediate results; nonzero divisors.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The expression is always valid, and it has no brackets and no rule about which operator goes first, so one pass from left to right is enough. Notice when a number can be used: not when you read it, but only later, when its operator arrives.

2. Hint 2: Ask a smaller question

   Work out "4 13 5 / +" by hand. When you reach the "/", which two numbers does it use? Where do you keep the 4 in the meantime, and when is it finally used?

3. Hint 3: Name the pattern

   An operator always uses the two most recent values that are still unused, and its result becomes the most recent value in turn. Values leave in the opposite order to the one they arrived in. That is a last-in, first-out stack. Read the lesson on last-in, first-out stack.

4. Hint 4: State the invariant

   After each token, the stack holds the values of the finished parts of the expression that no operator has used yet, in the order they appeared. A valid expression ends with exactly one value on the stack.

5. Hint 5: Sketch the pseudocode

   Start with an empty stack. For each token: if it is not one of the four operators, turn it into a number and push it. Otherwise pop the right value, then the left value, work out left operator right, drop the fraction after a division, and push the result. Return the one value left.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Push operands onto a stack. For an operator, pop the right then left operand, compute the result, and push it back; truncate division toward zero.

The slow way

Find the first operator in the list, replace it and the two numbers before it with their result, and start again from the beginning. It is correct, but every replacement reads the list again and rewrites it, so the work grows with the square of the number of tokens.

The insight

Reading from left to right, an operator always applies to the two most recent values that have not been used yet. Its result then takes their place as the most recent value. So you only ever need the newest values, and a stack hands you exactly those.

Step by step

1. Keep a stack of the numbers still waiting for an operator. A number cannot be used when you read it, because its operator comes later. The stack keeps the unused numbers with the newest one on top.
2. A number goes on top of the stack to wait. Any token that is not one of the four operators is a number, including a negative one such as "-7". Tokens are strings, so the token is turned into a number before it is stored.
3. An operator takes the top two numbers; the right one comes off first. The right-hand value was pushed last, so it is popped first. The order matters for subtraction and division: "3 5 -" means 3 minus 5.
4. Apply the operator and push the result back as one number. The result stands in for the small expression that was worked out, so a later operator can use it like any other number. Division keeps only the whole part: 13 / 5 becomes 2.
5. The one number left is the value of the whole expression. Every operator replaced two numbers with one. In a valid expression that leaves exactly one number after the last token, and it is the answer.

The same numbered steps are the comments in each solution.

function solve(tokens) {
  // 1. Keep a stack of the numbers still waiting for an operator
  const s = [];
  for (const t of tokens) {
    // 2. A number goes on top of the stack to wait
    if (!["+", "-", "*", "/"].includes(t)) {
      s.push(Number(t));
      continue;
    }
    // 3. An operator takes the top two numbers; the right one comes off first
    const b = s.pop(),
      a = s.pop();
    // 4. Apply the operator and push the result back as one number
    s.push(
      t === "+"
        ? a + b
        : t === "-"
          ? a - b
          : t === "*"
            ? a * b
            : Math.trunc(a / b),
    );
  }
  // 5. The one number left is the value of the whole expression
  // (JavaScript can produce -0 here; it is reported as 0.)
  return s[0] === 0 ? 0 : s[0];
}

function solve(tokens: string[]): number {
  // 1. Keep a stack of the numbers still waiting for an operator
  const s: number[] = [];
  for (const t of tokens) {
    // 2. A number goes on top of the stack to wait
    if (!["+", "-", "*", "/"].includes(t)) {
      s.push(Number(t));
      continue;
    }
    // 3. An operator takes the top two numbers; the right one comes off first
    const b = s.pop()!,
      a = s.pop()!;
    // 4. Apply the operator and push the result back as one number
    s.push(
      t === "+"
        ? a + b
        : t === "-"
          ? a - b
          : t === "*"
            ? a * b
            : Math.trunc(a / b),
    );
  }
  // 5. The one number left is the value of the whole expression
  // (JavaScript can produce -0 here; it is reported as 0.)
  return s[0] === 0 ? 0 : s[0];
}

def solve(tokens):
    # 1. Keep a stack of the numbers still waiting for an operator
    stack = []
    for token in tokens:
        # 2. A number goes on top of the stack to wait
        if token not in ("+", "-", "*", "/"):
            stack.append(int(token))
            continue
        # 3. An operator takes the top two numbers; the right one comes off first
        right = stack.pop()
        left = stack.pop()
        # 4. Apply the operator and push the result back as one number
        if token == "+":
            stack.append(left + right)
        elif token == "-":
            stack.append(left - right)
        elif token == "*":
            stack.append(left * right)
        else:
            # Truncate toward zero; // would round toward negative infinity.
            stack.append(int(left / right))
    # 5. The one number left is the value of the whole expression
    return stack[0]

Example 2, traced

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

Output
6

Why it works

Each operator must apply to the two values written before it, and those are the two newest unused values, which is what the top of the stack holds. Pushing the result back lets it serve as a value for a later operator, exactly as the notation intends.

Time and space

Time O(n), extra space O(n). Each token is handled once with a constant amount of work: one push, or two pops and a push. That is O(n) time for n tokens. If all the numbers come before the operators, about half of the tokens sit on the stack at once: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• The first value you pop is the right-hand one. Swapping the two turns "3 5 -" into 2 instead of -2, and example 2 into 4 instead of 6.
• Division must drop the fraction, not round down. For -7 / 3 the answer is -2, but Python's // operator and JavaScript's Math.floor both give -3.
• Recognize a number by checking that the token is not an operator. A test for digits fails on negative numbers such as "-7", which would be taken for an operator.

Pattern

Last-in, first-out stack. Builds on Valid Parentheses.

Keep going