Evaluate Reverse Polish Notation
You get an arithmetic expression in reverse Polish notation, as an array of tokens. In this notation every operator comes right after its two operands, so 3 4 + means 3 + 4 and 3 4 + 2 * means (3 + 4) * 2, with no parentheses needed. Each token is an integer or one of the operators +, -, * and /.
Evaluate the expression and return its value. Division keeps only the integer part and truncates toward zero: 7 / 2 is 3 and -7 / 2 is -3.
Function
- tokensstring-array
- the numbers and operators of the expression, in order
- Returnsinteger
- the value of the expression
Constraints
1 ≤ tokens.length ≤ 104- Each token is
+,-,*,/, or an integer from-200to200written in decimal, with a leading minus sign when it is negative. tokensis a valid expression in reverse Polish notation.- No division by zero happens, and every intermediate and final value is greater than
-231and less than231.
Examples
- Input
- tokens = ["8", "3", "-", "4", "*"]
- Output
- 20
- Explanation
- The
-applies to the two numbers before it in their order, 8 then 3, so it gives 5, not -5. Then*multiplies that 5 by 4, which gives 20.
- Input
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- Output
- -6
- Explanation
- The first operator,
/, uses the two most recent values: 9 divided by 3 is 3. Then-computes 2 minus that 3, which is -1, and*multiplies 6 by -1.
- Input
- tokens = ["10", "-7", "2", "/", "+"]
- Output
- 7
- Explanation
- The token
-7is a number, not an operator. -7 divided by 2 is -3.5, which truncates toward zero to -3 rather than rounding down to -4, and 10 plus -3 is 7.
+18 hidden tests on Submit
Follow-up
Can you rebuild the expression in ordinary notation, such as (3 + 4) * 2, adding parentheses only where they change the meaning?
Hints
Open them one at a time. Each one gives away a little more.
Read the tokens from left to right. When you meet an operator, which two values does it apply to? Look at the order in which those values were produced.
An operator always applies to the two most recent values that no operator has used yet, and its result becomes a new value for the operators that follow. "The most recent one not used yet" is exactly what a stack gives you.
Push every number. On an operator, pop the right operand first and the left operand second, combine them in that order, and push the result. When the tokens run out, the stack holds one value: the answer. Make sure your division truncates toward zero.
Solution
Reverse Polish notation needs no parentheses because the order of the tokens already fixes the order of the work: each operator applies to the two values right before it, and either of those values may be the result of an earlier operator. A stack of values evaluates the whole expression in one left to right pass. The traps are in the details: the order of the operands for - and /, telling the operator - apart from the number -7, and division that truncates toward zero.
Collapse the first operator, repeat
Correct, but does not finish on the largest tests
Intuition
This is how you would work it out on paper. Find the leftmost operator. No operator comes before it, so the two tokens right before it are plain numbers, and they are its operands. Compute the result and replace those three tokens with one number. The expression is now shorter and still means the same thing. Repeat until a single number is left.
Take ["6", "2", "9", "3", "/", "-", "*"]. The first operator is /, so 9 3 / becomes 3: ["6", "2", "3", "-", "*"]. Then 2 3 - becomes -1: ["6", "-1", "*"]. Then 6 -1 * becomes -6, the answer.
It is correct because each round replaces a complete piece a b op with its value, and the operators after it see that value exactly where the piece stood. It is slow because every round searches from the start again and then closes a gap in the middle of the array. With 5,000 numbers followed by 4,999 operators, the first operator sits about halfway along for all 4,999 rounds, so the searches alone check about 1.25 × 10^7 tokens. The numbers to the left of the operator barely change from one round to the next, yet every round reads them again.
Algorithm
- Copy the tokens into a list you can change.
- Scan from the start to the first operator, at position
k. - Apply it to the numbers at
k-2(left) andk-1(right). - Replace the three tokens at
k-2,k-1andkwith the result. - Repeat until one token is left, and return it as a number.
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])One pass with a stack of values
Intuition
The collapse approach keeps rereading the numbers to the left of the operator. Keep them on a stack instead. Read the tokens once, from left to right. A number goes onto the stack. An operator takes the top two values off the stack, combines them, and puts the result back, where it waits for the next operator like any other value.
Walk through ["6", "2", "9", "3", "/", "-", "*"]. The four numbers go on the stack: [6, 2, 9, 3]. The / pops 3 and then 9 and pushes 9 / 3 = 3: [6, 2, 3]. The - pops 3 and then 2 and pushes 2 - 3 = -1: [6, -1]. The * pops -1 and then 6 and pushes 6 * -1 = -6. One value is left, and it is the answer.
Why it works: at every moment the stack holds the values of the complete pieces read so far, in order, and an operator always applies to the last two of them. The top of the stack is the right operand, because it was produced last, so pop it first. Getting that order wrong only shows up with - and /, where 8 3 - must be 5 and not -5.
Division needs care in some languages. The expression truncates toward zero, but Python's //, Ruby's / and R's %/% round down, which turns -3.5 into -4. Each number is pushed once and each operator pops two values and pushes one, so the pass takes O(n) time, and the stack never holds more than n values.
Algorithm
- Start with an empty stack.
- For each token that is a number, push its value.
- For each operator, pop the right operand, then the left operand.
- Compute
left op right, truncating toward zero for/, and push the result. - After the last token, return the single value on the stack.
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
Pitfalls and edge cases
The stack loop is short; most wrong answers come from the order of the operands and from how a language divides.
- Swapping the operands. The first pop is the right operand:
["3", "5", "-"]is -2, and["2", "9", "/"]is 0, not 4. - Spotting operators by their first character.
-7starts with a minus sign but is a number. Compare the whole token, or check that it is one character long. - Rounding down instead of truncating.
-7 / 2must give -3, and-1 / 3must give 0. Python's//, Ruby's/, R's%/%and Lua'smath.floorgive -4 and -1. - Printing
-0. In JavaScript and Lua every number is a float, so0 * -5andMath.trunc(-1 / 3)give negative zero, which prints as-0. Add 0 to the final value to turn it into 0. - Reading a number one digit at a time. Tokens such as
13and-200have several characters; parse the whole token. - Assuming the last token is an operator. A single number such as
["7"]is a valid expression whose value is 7.
Frequently asked questions4
What is the time complexity of Evaluate Reverse Polish Notation?
The stack solution runs in O(n) time for n tokens: each number is pushed once, and each operator does two pops and one push. The stack can hold up to about n/2 values, so the space is O(n). Collapsing the first operator over and over takes O(n²) time, because every round searches from the start again.
Why does reverse Polish notation need no parentheses?
In ordinary notation, 3 + 4 * 2 needs a precedence rule or parentheses to say which operation comes first. In reverse Polish notation an operator always applies to the two values right before it, so the order of the tokens says it all: 3 4 2 * + is 11 and 3 4 + 2 * is 14. That is why a single stack can evaluate it without ever looking ahead.
How do you divide with truncation toward zero in Python?
Use int(a / b). The // operator rounds down, so -7 // 2 is -4, while int(-7 / 2) is -3. The float division is exact enough here because the values fit in 32 bits. For arbitrary large integers, divide the absolute values with // and put the sign back afterwards.
How do you turn an ordinary expression into reverse Polish notation?
The shunting-yard algorithm does it in one pass with a stack of operators. Numbers go straight to the output. Before an operator is pushed, every operator on the stack with higher or equal precedence is moved to the output; an opening parenthesis is pushed, and a closing one moves operators to the output until it meets its partner. At the end, the remaining operators go to the output.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def evalRPN(tokens):
# Write code hereCase 1
Case 2
Case 3
Input
tokens = ["8", "3", "-", "4", "*"]
Expected
20