Evaluate Reverse Polish Notation

Medium#150evaluate

You get an arithmetic expression in reverse Polish notation, as a list of tokens: integers and the operators + − × ÷, each operator after its two operands. Work out its value. Division keeps only the integer part, rounding towards zero, and the expression is always correct. Our example: 3 10 − 4 × 5 ÷, which is (3 − 10) × 4 ÷ 5 — the answer is −5.

150 Evaluate Reverse Polish NotationWalkthrough · 1×

Example: 3 10 − 4 × 5 ÷. Under the tokens is the stack of numbers, newest on the right, and under it the operation being worked out.

tokens031102−344×556÷nums—
not read yett, read now; the number just pushedon the stackpopped operandsreadthe answer

Start with an empty stack of numbers

01/25
restart · back · play · step
Speed
1function evalRPN(tokens):
2 nums = empty stack
3 for each t in tokens:
4 if t is an operator:
5 right = pop from nums
6 left = pop from nums
7 push calc(left, t, right) onto nums
8 else:
9 push int(t) onto nums
10 return the only number in nums
state
tokens
["3", "10", "-", "4", "*", "5", "/"]
nums
[]
t
–
left
–
right
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. In this notation an operator always comes right after its two operands are complete, so they are the two newest numbers: the top two of the stack.
  2. The result goes back as one number, which is exactly what the next operator may need as an operand, so the expression folds up from the inside out.
  3. The top was written last, so it is the right operand: for − and ÷ the first pop goes on the right. Truncating towards zero keeps −5.6 as −5.

Complexity

Time O(n): each token is read once, and a push or a pop is O(1). Memory O(n): when the numbers come first, most of them wait on the stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.