Problem overview
In reverse Polish notation, also called postfix notation, an operator comes after its two operands. 3 + 4 is written 3 4 +, and (1 + 2) * 3 is written 1 2 + 3 *. No parentheses are needed: the order of the tokens alone says what is computed first.
The method evalRPN receives a String[] called tokens holding a valid expression, and returns its value as an int. Each token is an operator ("+", "-", "*" or "/") or an integer such as "42" or "-7". An operator works on the two values right before it, once they are worked out. The first is its left operand and the second its right operand, so 8 3 - means 8 - 3 = 5, not 3 - 8. Division truncates toward zero: 7 / 2 is 3 and -7 / 2 is -3.
["2","1","+","3","*"]gives 9, since (2 + 1) * 3 = 9.["4","13","5","/","+"]gives 6: 13 / 5 is 2, and 4 + 2 is 6.["10","6","9","3","+","-11","*","/","*","17","+","5","+"]gives 22. Inside it, 6 / (12 * -11) is 6 / -132, which truncates to 0.
The statement asks for O(n) time and O(n) extra space.
Approach: a stack of values
Read the tokens from left to right. A number can't be used until an operator arrives, so it waits. When an operator arrives, its operands are the two most recent values not used yet. That is the definition of the top two items of a stack.
- A number is pushed.
- An operator pops two values, computes, and pushes the result. The result takes the place of its two operands, and a later operator may use it as an operand.
Because every operator turns two values into one, a valid expression ends with exactly one value on the stack: the answer. Each token is handled once, so the time is O(n). Here is the stack after each token of the first example:
after 2: [2]
after 1: [2, 1]
after +: [3]
after 3: [3, 3]
after *: [9]
The top of the stack is the right end of each list.
Step by step
- Create the stack:
Stack<Integer> stack = new Stack<>(). It holds the values worked out so far. - Loop over the tokens with
for (String token : tokens). - Detect an operator: compare
tokenwith"+","-","*"and"/", joined with||, usingequals. A negative number such as"-7"also starts with a minus sign, but it is not equal to the one-character token"-". - Pop the right operand first:
int b = stack.pop(). It was worked out last, so it is on top. - Pop the left operand:
int a = stack.pop(). Poppingbfirst andasecond keeps the meaning of the expression:8 3 -isa - b. - Addition: if
tokenis"+", pusha + b. - Subtraction: else if it is
"-", pusha - b. The order matters here. - Multiplication: else if it is
"*", pusha * b. - Division: the final
elseis the last operator, so pusha / b. - Numbers: the
elseof the firstifpushesInteger.parseInt(token), which turns"-7"into the int -7. - Return the result: after the loop,
stack.pop()gives the one value left.
The solution in Java
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
int b = stack.pop();
int a = stack.pop();
if (token.equals("+")) {
stack.push(a + b);
} else if (token.equals("-")) {
stack.push(a - b);
} else if (token.equals("*")) {
stack.push(a * b);
} else {
stack.push(a / b);
}
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
Java details worth a closer look:
- Compare strings with
equals.==on two strings checks whether they are the same object, not whether they hold the same characters. Witha = "-"andb = new String("-"),a == bisfalseanda.equals(b)istrue. Tokens in an array can come from anywhere, soequalsis the safe choice. - Division truncates toward zero. Java's
/on twoints drops the fraction, so-7 / 2is-3, which is what the statement asks for.Math.floorDiv(-7, 2)would give-4, the wrong answer here. - Boxing. A
Stack<Integer>holdsIntegerobjects.stack.push(a + b)boxes theintresult andint b = stack.pop()unboxes it. Integer.parseInt. It accepts a leading minus sign, so negative numbers need no special handling. It throws aNumberFormatExceptionfor text that isn't a number, which can't happen with valid input.- Overflow. The statement promises every value fits in a 32-bit
int, so plainintarithmetic is enough. For example,["2147483647","1","-"]gives2147483646. Stack. It is an older class, andArrayDequeis the usual modern choice.Stackworks the same way here:pushadds on top andpopremoves the top.
Complexity
Time: O(n). Every token is read once, and each push and pop takes constant time.
Space: O(n). In the worst case, such as a list of numbers followed by all the operators, nearly every token waits on the stack at once.
Edge cases and common mistakes
- A single number.
["42"]gives 42, and["-7"]gives -7. No operator ever runs. - Operand order.
["8","3","-"]gives 5. Swappingaandbwould give -5, and for division the answer would be wrong too. - Negative division.
["-7","2","/"]gives -3, while["7","2","/"]gives 3. - Negative operands.
["3","-4","*"]gives -12. The token"-4"is a number, not an operator, because it isn't equal to"-". - Testing the operator with
startsWith("-")or==. The first treats every negative number as a minus sign. The second may compare references and fail. - Popping in the wrong order. Taking
abeforebreverses the operands, which breaks subtraction and division.
Testing
["2","1","+","3","*"]gives9.["4","13","5","/","+"]gives6.["10","6","9","3","+","-11","*","/","*","17","+","5","+"]gives22.["8","3","-"]gives5.["-7","2","/"]gives-3.["1","2","+","3","*"]gives9.
