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, because the order of the tokens says what to compute first.
The function evalRPN(tokens: Array<String>): Int receives a valid expression as an array of strings and returns its value. Each token is one of the operators "+", "-", "*", "/", 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, the second its right one, so 8 3 - is 8 - 3 = 5. Division truncates toward zero, so -7 / 2 is -3.
For ["2", "1", "+", "3", "*"] the result is 9, since (2 + 1) * 3 = 9. For ["4", "13", "5", "/", "+"] it is 6, since 13 / 5 is 2 after truncation and 4 + 2 = 6.
The lesson asks for O(n) time and O(n) extra space, where n is the number of tokens.
Approach: a stack of values worked out so far
Read the tokens from left to right. A number can't be used until an operator asks for it, so it waits. When an operator arrives, its operands are the two most recent values that haven't been used yet. That is exactly what the top of a stack holds: the last value pushed is the first one popped.
So the rule has two cases:
- A number: push it.
- An operator: pop two values, apply the operator, and push the result. The result takes the place of its two operands, and a later operator may use it as one of its own.
Every operator turns two values into one, so a valid expression ends with exactly one value on the stack: the answer. Each token is handled once with constant work, which gives O(n) time, and the stack never holds more than n values.
The order of the pops matters. The right operand was computed last, so it is on top and comes off first. Pop it into b, then pop a, and compute a - b or a / b. Swapping them would turn 8 3 - into 3 - 8.
Here is the stack for ["4", "13", "5", "/", "+"]:
token 4: stack=[4]
token 13: stack=[4, 13]
token 5: stack=[4, 13, 5]
token /: a=13 b=5 stack=[4, 2]
token +: a=4 b=2 stack=[6]
Step by step
- Create the stack: a
valnamedstack, an emptyArrayDeque<Int>().addLastandremoveLastboth work at the end, so the end is the top. - Loop over the tokens, from left to right, one at a time.
- Test for an operator by comparing the token with each of the four operator strings, joined with
||. A negative number such as"-7"starts with a minus sign, but it isn't equal to the one-character string"-", so it isn't mistaken for the operator. - Pop the right operand with
removeLast()intob. - Pop the left operand into
a. - For
"+", pusha + b. - For
"-", pusha - b, where the order matters. - For
"*", pusha * b. - Otherwise it is
"/", so pusha / b. Kotlin's integer division already truncates toward zero. - For a number, push
token.toInt(). It sits on the stack until an operator uses it. - Return the last value, taken with
removeLast().
The solution in Kotlin
class Solution {
fun evalRPN(tokens: Array<String>): Int {
val stack = ArrayDeque<Int>()
for (token in tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
val b = stack.removeLast()
val a = stack.removeLast()
if (token == "+") {
stack.addLast(a + b)
} else if (token == "-") {
stack.addLast(a - b)
} else if (token == "*") {
stack.addLast(a * b)
} else {
stack.addLast(a / b)
}
} else {
stack.addLast(token.toInt())
}
}
return stack.removeLast()
}
}
Kotlin details worth a look:
ArrayDequeas a stack. It is Kotlin's ownkotlin.collections.ArrayDeque, available without an import.addLastpushes andremoveLastpops, both in constant time.removeLaston an empty deque throwsNoSuchElementException, which can't happen for a valid expression.- String comparison.
==in Kotlin compares contents (it callsequals), sotoken == "+"is the right test."-" == "-7"isfalse, which is why negative numbers go to the number branch. - Truncating division. On
Ints,/drops the fraction toward zero:-7 / 2is-3, and7 / -2is-3too. Rounding down instead would give-4for the first.Math.floorDiv(-7, 2)is that rounding-down version, and it isn't what this problem wants. toInt()."-7".toInt()is-7. It throwsNumberFormatExceptionfor text that isn't an integer, but the tokens here are valid.Intarithmetic. Results are 32-bit and overflow wraps silently. The lesson guarantees every intermediate value fits, so no wider type is needed.- The
ifchain. The lastelsehandles"/"because the earlier tests have already ruled out the other three operators.
Complexity
Time: O(n). Each token is read once. Pushing, popping and the arithmetic are constant-time operations.
Space: O(n). In the worst case, such as many numbers followed by many operators, the stack holds a large share of the tokens at once.
Edge cases and common mistakes
- Operand order.
["8", "3", "-"]returns 5. Computingb - agives -5. - Division of negative numbers.
["-7", "2", "/"]returns -3, and["7", "-2", "/"]returns -3.["-7", "-2", "/"]returns 3. - A lone number.
["-7"]returns -7: no operator runs, and the one value on the stack is the answer. - Telling
"-"from"-11". Checking only the first character, or usingstartsWith("-"), would treat negative numbers as operators. Comparing the whole token avoids that. - Result that truncates to zero. In the third lesson example,
6 / -132becomes 0, and the expression finishes at 22. - Reading the stack at the end. After the loop, exactly one value should remain. The function removes it rather than peeking, because only one is left.
Testing
["2", "1", "+", "3", "*"]gives9.["4", "13", "5", "/", "+"]gives6.["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]gives22.["8", "3", "-"]gives5.["-7", "2", "/"]gives-3.["-7"]gives-7.
