Problem: Evaluate Reverse Polish Notation

Let’s try another classic stack problem: evaluating an expression in Reverse Polish Notation.

What is Reverse Polish Notation? It comes from compilers and calculators. The arithmetic notation we normally use is called infix notation: the operator sits between its operands, as in 2 + 3. Infix notation needs parentheses and precedence rules to be unambiguous: (2 + 1) * 4 and 2 + 1 * 4 are different expressions, and the parentheses tell them apart.

There is another notation that does not need parentheses or precedence rules. In postfix notation, better known as Reverse Polish Notation (RPN), the operator comes after its two operands. The expression 2 1 + means 2 + 1. The expression (2 + 1) * 4 becomes:

2 1 + 4 *

Read it left to right: 2 1 + evaluates to 3, and then 3 4 * evaluates to 12. The operands of * are the result of 2 1 + and the number 4.

In this problem, each token is either an integer or one of the four operators +, -, *, and /. The division between two integers truncates toward zero, as Java’s integer division does.

Here are some examples:

• ["2", "1", "+", "4", "*"] evaluates to 12, since (2 + 1) * 4 = 12.
• ["4", "13", "5", "/", "+"] evaluates to 6, since 4 + (13 / 5) = 4 + 2 = 6. Note the integer division: 13 / 5 is 2, not 2.6.
• ["42"] evaluates to 42. A single number is a valid expression.

The signature of the method in Java might look like this:

public static int evalRPN(String[] tokens) {
  // Your implementation goes here
}

As with valid parentheses, we want to solve this in $O(n)$ time, where $n$ is the number of tokens.

There are two details to note before we try a solution:

• Subtraction and division are not commutative, so the order of the operands matters. The expression a b - means a - b, not b - a. For example, ["7", "3", "-"] evaluates to 4.
• The tokens are strings, and a number token can be negative, such as "-3". This is one reason the input comes as an array of tokens rather than one string of characters: the - in -3 is part of the number, while a - standing alone is the subtraction operator.

Assume the input is guaranteed to be a valid RPN expression, so we do not need to handle malformed input, such as an operator without enough operands.