Problem overview
In reverse Polish notation (postfix), 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 is computed first.
The method evalRPN receives tokens, an Array[String] holding a valid expression, and returns its value. A token is an operator ("+", "-", "*" or "/") or an integer such as "42" or "-7". An operator works on the two values right before it: the first is its left operand and the second its right operand, so 8 3 - is 8 - 3 = 5. Division truncates toward zero, so 7 / 2 is 3 and -7 / 2 is -3.
For ["2", "1", "+", "3", "*"] the answer is 9: first 2 + 1 = 3, then 3 * 3 = 9.
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 that haven't been used yet, which are exactly the two values on top of a stack. Pop them, apply the operator, and push the result, which now waits for the next operator.
Each token is read once and each push or pop costs O(1), so the whole evaluation takes O(n) time and O(n) space for the stack.
A valid expression turns every operator's two values into one, so at the end exactly one value remains on the stack: the result.
Step by step
- Create the stack:
val stack = scala.collection.mutable.Stack[Int](). It holds the values worked out so far, the most recent on top. - Loop over the tokens with
for (token <- tokens), left to right. - Detect an operator by comparing
tokenwith the four one-character strings, joined with||. A negative number such as"-7"starts with a minus sign but isn't equal to"-", so it is not mistaken for an operator. - Pop the right operand first into
b: it was worked out last, so it is on top. - Pop the left operand into
a. Poppingbbeforeakeeps the order the expression means:8 3 -isa - b. - Apply
+by pushinga + b. - Apply
-by pushinga - b. The order matters here. - Apply
*by pushinga * b. - Apply
/in the finalelseby pushinga / b. Integer division in Scala truncates toward zero, as the lesson requires. - Handle numbers in the outer
else: pushtoken.toInt. - Return the result by popping the one value left on the stack.
The solution in Scala
class Solution {
def evalRPN(tokens: Array[String]): Int = {
val stack = scala.collection.mutable.Stack[Int]()
for (token <- tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
val b = stack.pop()
val a = stack.pop()
if (token == "+") {
stack.push(a + b)
} else if (token == "-") {
stack.push(a - b)
} else if (token == "*") {
stack.push(a * b)
} else {
stack.push(a / b)
}
} else {
stack.push(token.toInt)
}
}
return stack.pop()
}
}
The Scala details worth a closer look:
==compares strings by value.token == "+"is true whenever the text is a plus sign. This is unlike Java's==on objects, which compares references.- Division truncates toward zero.
-7 / 2is-3, and7 / -2is also-3. The remainder keeps the sign of the left operand:-7 % 2is-1. Floor division would give-4(Math.floorDiv(-7, 2)), which is not what the lesson wants, so the plain/is right. toIntaccepts a leading minus."-7".toIntis-7. A string that isn't a number, such as"+", throws aNumberFormatException, which is why operators are checked first.pop()andpushwork at the top. The mutableStackremoves and returns the most recently pushed element withpop(). Popping an empty stack throws an exception, which a valid expression never causes.Intoverflow wraps silently in Scala:Int.MaxValue * 2is-2. The constraints promise that every value fits in 32 bits, soIntis enough.return stack.pop()could also be written withoutreturn, as the method's last expression.- The class name. It's written in full,
scala.collection.mutable.Stack, so the code needs no import.Stackis not available without the package name or an import.
Complexity
Time: O(n). Every token is read once, and each token costs a constant number of stack operations and one arithmetic step or one toInt.
Space: O(n). In the worst case, such as 1 2 3 4 + + +, the stack holds most of the numbers before the operators arrive.
Edge cases and common mistakes
- Operand order.
["8", "3", "-"]gives 5. Swappingaandbgives -5. The same applies to/. - Negative numbers.
["3", "-4", "*"]gives -12. The token"-4"goes totoInt, not to the operator branch. - Rounding of division.
["7", "2", "/"]gives 3 and["-7", "2", "/"]gives -3. In the long example, 6 / -132 is about -0.045 and truncates to 0, so the product becomes 0 and the final answer is 22. - A single number.
["42"]gives 42, and["-7"]gives -7: the number is pushed and then popped as the result. - Nested expressions.
["1", "2", "3", "*", "+"]gives 7: the*uses 2 and 3 first, and the+uses 1 and their product. - Testing for operators with
startsWith("-"). That treats every negative number as a subtraction. Compare with the whole token.
Testing
["2", "1", "+", "3", "*"]gives 9.["4", "13", "5", "/", "+"]gives 6.["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]gives 22.["8", "3", "-"]gives 5.["-7", "2", "/"]gives -3.["42"]gives 42.
