Coding interview problems › Stack & Monotonic Stack

📚 Stack & Monotonic Stack Medium

Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation (postfix) with a stack: push numbers, pop two on each operator, and truncate division toward zero. Tested Python, live visual.

Also searched as: postfix expression evaluation using stack · evaluate postfix expression · RPN calculator

📚

Try it live Free

Stacks & the Monotonic Stack

Run the stack mode and watch values pile up and come off the top in last-in, first-out order, which is exactly how operands are consumed here.

Open the playground →

The problem

You are given an arithmetic expression in postfix (Reverse Polish) form as a list of tokens, for example ["4", "13", "5", "/", "+"]. Tokens are integers or one of + - * /. Evaluate it and return the integer result, where division truncates toward zero. The expression is always valid.

Inputtokens = ["4", "13", "5", "/", "+"]
Output6

13 / 5 = 2 (truncated), then 4 + 2 = 6.

Inputtokens = ["2", "1", "+", "3", "*"]
Output9

(2 + 1) * 3

The key insight

In postfix notation an operator always applies to the two most recent values that have not been used yet. A stack keeps exactly those values on top: push numbers, and when an operator arrives, pop two, combine them, and push the result back.

Brute force first: Converting the expression back into a fully bracketed infix string and evaluating it is far more work and easy to get wrong; the stack evaluation is already the direct method.

Step-by-step approach

  1. Create an empty stack.
  2. For each token that is a number, push int(token).
  3. For an operator, pop b first and then a; the order matters for - and /.
  4. Compute a op b; for division use int(a / b) so the result truncates toward zero.
  5. Push the result. At the end the single value left on the stack is the answer.

Python solution

PYTHON 3tested
def eval_rpn(tokens):
    stack = []
    for tok in tokens:
        if tok in ("+", "-", "*", "/"):
            b = stack.pop()                 # right operand comes off first
            a = stack.pop()
            if tok == "+":
                stack.append(a + b)
            elif tok == "-":
                stack.append(a - b)
            elif tok == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))    # truncate toward zero
        else:
            stack.append(int(tok))
    return stack[0]

Complexity

TimeO(n)
SpaceO(n)

Each token is processed once with constant work. The stack can hold up to about n/2 numbers before operators start reducing it.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(n) time, one pass over the tokens, and O(n) space for the stack.

Why does int(a / b) truncate correctly?

a / b gives a float and int() drops the fractional part, which rounds toward zero for both positive and negative results. For very large integers, a safer exact form is to compute abs(a) // abs(b) and then apply the sign.

Why is postfix notation useful?

It needs no brackets and no precedence rules, so a machine can evaluate it with one stack in a single pass. Compilers and calculators often convert infix to postfix first.

How do I convert an infix expression to postfix?

Use the shunting-yard algorithm: output numbers directly, and keep operators on a stack, popping those with higher or equal precedence before pushing a new one.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Stack & Monotonic Stack Stacks & the Monotonic Stack lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.