Evaluate Reverse Polish Notation
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Evaluate an arithmetic expression written in reverse Polish notation (operators come after their numbers).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1In "2 1 +" which numbers does the + work on?
- Hint 2Keep the numbers waiting for an operator in a stack.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A calculator with a tray. Numbers are put on the tray one on top of the other. When an operator like + arrives, you take the top two numbers off the tray, do the sum, and put the result back on the tray. When the expression ends, the single number left on the tray is the answer.
- The obvious way
Convert to normal (infix) notation with brackets first: lots of extra work.
- The key insight
Read the tokens left to right. A number goes on the stack. An operator takes the top two numbers off (the first one taken is the right-hand operand), applies itself, and pushes the result. Division truncates toward zero. One number remains at the end.
- The algorithm
- Empty tray.
- Token is a number? Put it on the tray.
- Token is an operator? Take the top two numbers (right operand first), calculate, put the result back.
- At the end the only number on the tray is the answer.
Watch it run
Exampletokens = ["2", "1", "+", "3", "*"]
2 and 1 are numbers: put them on the tray.
tray: 2, 1
Where people slip
- For - and / the order matters: the first number popped is the RIGHT operand.
- Python's // floors toward minus infinity; use int(left / right) to truncate toward zero.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def eval_rpn(tokens):
tray = []
for token in tokens:
if token in ("+", "-", "*", "/"):
right = tray.pop() # the first one taken is the right operand
left = tray.pop()
if token == "+":
tray.append(left + right)
elif token == "-":
tray.append(left - right)
elif token == "*":
tray.append(left * right)
else:
tray.append(int(left / right)) # truncates toward zero
else:
tray.append(int(token))
return tray[0]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.