Workspace

Problem workspace

3 day streakD

Evaluate Reverse Polish Notation

MediumStacksExpressions & parsing

The challenge

Evaluate a valid postfix expression containing integer operands and +, -, *, /.

Tokens are space-separated. Division truncates toward zero. No division by zero; intermediates fit signed 32-bit integers.

Example

2 1 + 3 * → 9.

Use the walkthrough below to inspect the input and each state change.

See Evaluate Reverse Polish Notation, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.2011+233*4Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 7

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: ["2","1","+","3","*"]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

Operands wait on the stack until an operator consumes the top two.

Indices are zero-based. C++ uses C++17 or later.

def solve(tokens):
    stack = []
    for token in tokens:
        if token not in ('+', '-', '*', '/'):
            stack.append(int(token))
            continue
        right, left = stack.pop(), stack.pop()
        if token == '+': value = left + right
        elif token == '-': value = left - right
        elif token == '*': value = left * right
        else:
            value = abs(left) // abs(right)
            if (left < 0) != (right < 0): value = -value
        stack.append(value)
    return stack[0]

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap