Solution: Reducing the First Operator

How would we evaluate an RPN expression by hand? In the example 2 1 + 4 *, we found the operator +, applied it to the two numbers before it, and replaced the three tokens 2 1 + with the result 3. Then we did it again with *. Let’s turn this into an algorithm: find the first operator, apply it to the two tokens before it, replace the three tokens with the result. Now you have a shorter expression that is still valid RPN. Repeat until one token remains. That final token is the value of the expression, which we return as the answer.

Let’s trace it on ["4", "13", "5", "/", "+"]:

4 13 5 / +   first operator is /, apply 13 / 5
4 2 +        first operator is +, apply 4 + 2
6            one token left: the value is 6

To implement this, we need to remove tokens from the middle of a sequence. We copy the tokens into a new array and keep a size count of how many slots are still in use. Removing a token means shifting every later token one position left and decreasing size by one. We put that in a helper called removeAt, the same shifting loop we wrote for the dynamic array in Chapter 1:

private static int removeAt(String[] list, int size, int index) {
  for (int k = index; k < size - 1; k++) {
    list[k] = list[k + 1];
  }
  return size - 1;
}

Using removeAt, we reduce the array until one token remains:

public static int evalRPN(String[] tokens) {
  String[] list = new String[tokens.length];
  int size = tokens.length;
  for (int i = 0; i < tokens.length; i++) {
    list[i] = tokens[i];  // copy so we do not change the caller's array
  }

  while (size > 1) {
    int i = 0;
    while (!isOperator(list[i])) {
      i++;  // find the first operator
    }
    int a = Integer.parseInt(list[i - 2]);
    int b = Integer.parseInt(list[i - 1]);
    int result = apply(list[i], a, b);
    list[i - 2] = Integer.toString(result);
    size = removeAt(list, size, i);      // remove the operator first
    size = removeAt(list, size, i - 1);  // then the second operand
  }

  return Integer.parseInt(list[0]);
}

Integer.parseInt converts a token like "13" or "-3" to the int it names, and Integer.toString converts the result back to a token. The order of the two removeAt calls matters: removing shifts the later elements left, so we remove the operator at index i first, then the operand at index i - 1. In the other order, removing the operand would shift the operator before we get to it.

The other two helpers are short. Note that we compare strings with equals, not ==, as we learned in Chapter 2:

private static boolean isOperator(String token) {
  return token.equals("+") || token.equals("-")
      || token.equals("*") || token.equals("/");
}

private static int apply(String operator, int a, int b) {
  if (operator.equals("+")) return a + b;
  if (operator.equals("-")) return a - b;
  if (operator.equals("*")) return a * b;
  return a / b;  // the operator is "/"
}

Note the operand order in apply: a is the earlier token, at index i - 2.

The time complexity of this solution is $O(n^2)$. Each iteration of the outer loop scans for the first operator and shifts elements to close the gaps left by removeAt, which is $O(n)$ work. Each iteration replaces three tokens with one, shrinking size by two, so there are about $n/2$ iterations.

The array holds a copy of the tokens, so the auxiliary space complexity is $O(n)$.