Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Evaluate Reverse Polish Notation

LeetCode #150Medium
Operand stack · postfix evaluation

Evaluate an arithmetic expression in Reverse Polish (postfix) Notation. Valid operators are +, −, *, and /; division truncates toward zero. Return the integer the expression evaluates to.

Asked atAmazonLinkedInGoogle
step 1 / 9
2
1
+
3
*
[0][1][2][3][4]
top ↓
(empty)
operands
Operand stack
▸
1stack = []
2for token in tokens:
3    if token is a number:
4        stack.push(number(token))
5    else:                       // operator
6        right = stack.pop()
7        left  = stack.pop()
8        stack.push(left OP right)
9return stack.top()              // the only element
state
  • stack[]
  • actionstart

line 1Reverse Polish (postfix) notation puts each operator AFTER its two operands, so no brackets are needed. The classic tool is an operand stack: scan left→right, push every number, and when an operator appears pop the two operands it acts on, combine them, and push the result back.