Solution: Evaluating with a Stack

An operator always applies to the two most recent numbers before it that have not been used yet. The keyword here is “most recent,” which suggests a last-in, first-out (LIFO) structure like a stack.

Let’s scan the tokens once, left to right, and apply that rule directly.

When we see a number, we cannot do anything with it yet. Its operator comes later. We push it onto the stack and move on. When we see an operator, we pop the two most recently pushed numbers, apply the operator, and the result becomes a number we have not used yet, so we push it onto the stack.

At the end, the stack holds one number: the value of the expression.

Let’s trace this algorithm for ["7", "3", "-"]. We push 7, push 3, and at -, the stack looks like this:

┌───┐
│ 3 │ ◀── top
├───┤
│ 7 │
└───┘

The top is 3. So the first pop gives b and the second pop gives a, and we compute a - b: $7 - 3 = 4$ . Now push the result back onto the stack.

┌───┐
│ 4 │ ◀── top
└───┘

This is the result of the expression ["7", "3", "-"].

Here is the implementation. The helpers isOperator and apply are the same ones we wrote for the brute-force solution:

public static int evalRPN(String[] tokens) {
  Stack<Integer> stack = new ArrayStack<>();  // or new LinkedStack<>()

  for (int i = 0; i < tokens.length; i++) {
    String token = tokens[i];

    if (isOperator(token)) {
      int b = stack.top();  // the most recent number is the second operand
      stack.pop();
      int a = stack.top();
      stack.pop();
      stack.push(apply(token, a, b));
    } else {
      stack.push(Integer.parseInt(token));
    }
  }

  return stack.top();
}

Let’s trace it one more time on ["2", "1", "+", "4", "*"].

2 is a number: push it.

┌────┐
│  2 │ ◀── top
└────┘

1 is a number: push it.

┌────┐
│  1 │ ◀── top
├────┤
│  2 │
└────┘

+ is an operator: pop 1 and 2, push $2 + 1 = 3$ .

┌────┐
│  3 │ ◀── top
└────┘

4 is a number: push it.

┌────┐
│  4 │ ◀── top
├────┤
│  3 │
└────┘

* is an operator: pop 4 and 3, push $3 * 4 = 12$ .

┌────┐
│ 12 │ ◀── top
└────┘

We are out of tokens. The stack holds one number, and top returns 12.

What about the edge case ["42"]? The number is pushed, the loop ends, and top returns 42. And because the input is guaranteed to be a valid expression, we never pop from an empty stack and never end with more than one number on the stack.

We make one pass over the tokens. Each token causes at most one push and two pops, and every stack operation is $O (1)$ , with push amortized. So the total time is $O (n)$ , down from the brute-force solution’s $O (n^{2})$ . The auxiliary space is the stack, which in the worst case (all the numbers before any operator) holds about half the tokens: $O (n)$ .

In the valid parentheses problem and in this problem, the stack does the same thing. It stores the items we cannot process yet, and it returns the most recent one when it is needed. Keep this pattern in mind when designing algorithms that involve deferred processing.