← all entries
A-023● Day 232026.05.27mediumleetcode #150neetcode150

Evaluate Reverse Polish Notation

#array#math#stack
↗ leetcode #150 · evaluate-reverse-polish-notation
01

Problem

· problem
P.023

Evaluate Reverse Polish Notation

↗ leetcode #150

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression. Note that: - The valid operators are '+', '-', '*', and '/'. - Each operand may be an integer or another expression. - The division between two integers always truncates toward zero. - There will not be any division by zero. - The input represents a valid arithmetic expression in a reverse polish notation. - The answer and all the intermediate calculations can be represented in a 32-bit integer.

constraints
  • · 1 ≤ tokens.length ≤ 10⁴
  • · tokens[i] is either an operator (+, -, *, /) or an integer in range [-200, 200]
  • · Division truncates toward zero
  • · No division by zero
// paraphrased summary — see source for full text
examples
example 1input → output
["2","1","+","3","*"]
9
example 2input → output
["4","13","5","/","+"]
6
example 3input → output
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
22
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What does 'truncates toward zero' mean for division?
  • ☐
    Why is operand order critical for subtraction and division?
  • ☐
    Why is a stack ideal for evaluating Reverse Polish Notation?
  • ☐
    How do we distinguish negative operands like '-11' from the minus operator?
  • ☐
    How do we handle that + and * are commutative but - and / are not?
  • ☐
    Why convert to float division then int() instead of using //?
  • ☐
    Could we use recursion instead of iteration to evaluate RPN?
  • ☐
    Do we need to store every intermediate calculation result?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize stack
○
stack = []
○
queue = []
○
nums = {}
○
stack = None
step 2· Process tokens sequentially
○
for c in tokens:
○
for i in range(len(tokens)):
○
for c in reversed(tokens):
step 3· Addition (commutative operator)│ │ nested
○
stack.append(stack.pop() + stack.pop())
○
a, b = stack.pop(), stack.pop(); stack.append(a + b)
○
stack.append(stack[0] + stack[1])
step 4· Subtraction (order-dependent)│ │ nested
○
stack.append(b - a)
○
stack.append(a - b)
○
stack.append(stack.pop() - stack.pop())
step 5· Division (truncate toward zero)│ │ nested
○
stack.append(int(float(b) / a))
○
stack.append(b // a)
○
stack.append(int(b / a))
step 6· Push operand values│ │ nested
○
stack.append(int(c))
○
if c.isdigit(): stack.append(int(c))
○
stack.append(float(c))
step 7· Return final result
○
return stack[0]
○
return sum(stack)
○
return stack.pop()
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def evalRPN(self, tokens: List[str]) -> int:
3
        stack = []
4
        for c in tokens:
5
            if c == "+":
6
                stack.append(stack.pop() + stack.pop())
7
            elif c == "-":
8
                a, b = stack.pop(), stack.pop()
9
                stack.append(b - a)
10
            elif c == "*":
11
                stack.append(stack.pop() * stack.pop())
12
            elif c == "/":
13
                a, b = stack.pop(), stack.pop()
14
                stack.append(int(float(b) / a))
15
            else:
16
                stack.append(int(c))
17
        return stack[0]
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
["2","1","+","3","*"]
→
9
case 2
["4","13","5","/","+"]
→
6
case 3
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
→
22
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.