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 alone says what to compute first.
The method evalRPN receives tokens, a list of strings holding a valid expression, and returns its value. 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 those are worked out: the first is its left operand and the second its right operand, so 8 3 - is 8 - 3 = 5. Division of integers truncates toward zero, so 7 / 2 is 3 and -7 / 2 is -3.
For ["2", "1", "+", "3", "*"] the result is 9, which is (2 + 1) * 3. For ["4", "13", "5", "/", "+"] it is 6: 13 / 5 is 2.6, truncated to 2, and 4 + 2 is 6.
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, the two values it needs are the two most recent ones not used yet. That is exactly the top of a stack: the last value pushed is the first one taken off.
So the rule is short:
- A number: push it.
- An operator: pop two values, combine them, push the result.
The result goes back on the stack because the next operator may use it as an operand. Every operator turns two values into one, so a valid expression ends with exactly one value on the stack, the answer.
Here is the stack for ["4", "13", "5", "/", "+"]:
4: [4]
13: [4, 13]
5: [4, 13, 5]
/: 13 / 5 -> [4, 2]
+: 4 + 2 -> [6]
And here is the long example from the statement, ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]:
10: [10]
6: [10, 6]
9: [10, 6, 9]
3: [10, 6, 9, 3]
+: 9 + 3 -> [10, 6, 12]
-11: [10, 6, 12, -11]
*: 12 * -11 -> [10, 6, -132]
/: 6 / -132 -> [10, 0]
*: 10 * 0 -> [0]
17: [0, 17]
+: 0 + 17 -> [17]
5: [17, 5]
+: 17 + 5 -> [22]
The final value is 22. Note the division: 6 / -132 is about -0.045, and truncating toward zero gives 0.
Step by step
- Create an empty list named
stack. It holds the values worked out so far, the most recent on top. - Loop over each
tokenonce, from left to right. That makes the whole evaluationO(n). - Check for an operator with
token in ("+", "-", "*", "/"). A negative number such as"-7"also starts with a minus sign, but it isn't equal to the one-character token"-", so it is treated as a number. - Pop the right operand first into
b. It was worked out last, so it is on top. - Pop the left operand into
a. Poppingbfirst andasecond keeps the order the expression means:8 3 -isa - b. - Addition: if the token is
"+", appenda + b. - Subtraction: an
eliffor"-"appendsa - b. The order matters here. - Multiplication: an
eliffor"*"appendsa * b. - Division: the
elsehandles the last operator and appendsint(a / b), which truncates toward zero. - Numbers: an
elseat the level of the firstifappendsint(token). A number is its own value and waits on the stack. - Return the one value left, popped from the stack.
The solution in Python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token in ("+", "-", "*", "/"):
b = stack.pop()
a = stack.pop()
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
else:
stack.append(int(a / b))
else:
stack.append(int(token))
return stack.pop()
Python details worth a closer look:
- A list as a stack.
appendpushes onto the end andpop()removes and returns the last item, both in constant time. - Division that truncates.
/always gives a float, andint()drops the fraction, which rounds toward zero:int(-7 / 2)is -3. Floor division//rounds down instead:-7 // 2is -4. Both agree for positive results (7 // 2andint(7 / 2)are 3), so a solution using//passes the positive tests and fails the negative ones. For["-7", "2", "/"]this solution returns -3. - Converting tokens.
int("-7")is -7. The tokens are strings, so a number has to go throughintbefore it is pushed. Otherwisea + bwould join two strings instead of adding two numbers. - Checking membership in a tuple.
token in ("+", "-", "*", "/")compares the whole string with each item. The string"-"matches and"-11"doesn't. - Float precision.
a / bis a float, which holds integers exactly up to 2**53. The problem's values fit in 32 bits, far below that, soint(a / b)is exact.
Complexity
Time: O(n). Each token is read once, and each push and pop takes constant time.
Space: O(n). In the worst case, such as an expression that lists all its numbers before any operator, the stack holds about half the tokens at once.
Edge cases and common mistakes
- Operand order.
["8", "3", "-"]gives 5. Popping in the wrong order would compute3 - 8and give -5. The same holds for division. - A single number.
["-7"]gives -7: the loop pushes it and the last line pops it. - Negative operands.
["3", "-7", "-"]gives 10, which is3 - (-7). The token"-7"is a number and"-"is an operator. - Truncating division.
["7", "2", "/"]gives 3,["-7", "2", "/"]gives -3, and["7", "-2", "/"]gives -3. - Using
//. It floors, so-7 // 2is -4, one too low whenever the exact result is negative and not a whole number. - Testing for numbers with
isdigit()."-7".isdigit()isFalse, so negative numbers would be mistaken for operators. Testing for the operators is the safe direction. - Forgetting
int(token). The stack would hold strings."2" + "1"is"21", and a later-or*would raise aTypeError.
Testing
["2", "1", "+", "3", "*"]gives9.["4", "13", "5", "/", "+"]gives6.["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]gives22.["8", "3", "-"]gives5.["7", "2", "/"]gives3.["-7", "2", "/"]gives-3.["7", "-2", "/"]gives-3.["3", "-7", "-"]gives10.["-7"]gives-7.
