DSA PatternsStacksmedium9 min read

Stack-based Expression Evaluation

Stacks solve arithmetic expression evaluation by handling operator precedence and parentheses in O(n). Two canonical forms: Reverse Polish Notation (postfix) — straightforward operand stack; and infix expressions (Basic Calculator) — two stacks for numbers and operators, with precedence rules. Both reduce to the same push/pop rhythm.

#stack#expression#evaluation#RPN#postfix#infix#calculator#precedence#beginner#interview

Table of contents

Before we start
Picture this first (no code yet)
The actual problem — Part 1
The RPN evaluator (clean 15-line solution)
Watch the RPN evaluator, frame by frame
The actual problem — Part 2
Infix evaluation with parentheses (number + sign stack)
Watch the infix evaluator, frame by frame
Basic Calculator II: with and / (no parentheses)
Common traps
Check yourself
Practice problems

Before we start

Expression evaluation is one of the oldest applications of stacks — it's literally how every compiler and calculator you've ever used works. Interview versions appear in two flavors: Reverse Polish Notation (postfix, the easier form) and infix expressions (with operator precedence and parentheses). By the end you will be able to:

Write the RPN evaluator from memory in under 2 minutes.
Implement the infix Basic Calculator (with +, −, parentheses) using a number stack and a sign mechanism.
Handle multi-digit numbers and negative numbers correctly.

Picture this first (no code yet)

A real-life story

Imagine you are a cashier adding up a grocery receipt, but instead of a standard formula like 3 + 4 × 2, the receipt is written in a special notation: 3 4 2 × + — numbers first, operators after. This is postfix notation.

Your strategy: walk the receipt left to right. Every time you see a number, push it onto a tray. Every time you see an operator, take the top two items from the tray, apply the operator, and put the result back. By the end, the tray has exactly one item — the total.

The reason postfix is brilliant: it needs no parentheses and no precedence rules. The order of operations is encoded by the order of operators on the page. The stack handles it automatically.

The actual problem — Part 1

Evaluate Reverse Polish Notation (LC #150):

Evaluate a valid arithmetic expression in postfix notation.

["2","1","+","3","*"] → (2 + 1) * 3 = 9
["4","13","5","/","+"] → 4 + (13 / 5) = 6 (integer division truncates toward zero)

The RPN evaluator (clean 15-line solution)

def evalRPN(tokens):
    stack = []
    ops   = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),   # truncates toward zero (not floor!)
    }

    for token in tokens:
        if token in ops:
            b = stack.pop()    # right operand (pushed more recently)
            a = stack.pop()    # left operand
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))

    return stack[0]

Line-by-line narration:

stack — holds numbers waiting to be consumed by an operator.
ops dictionary — maps each operator string to a lambda. Clean: no if/elif chain.
if token in ops: — operator found. Pop the two most recent operands.
b = stack.pop() first, then a = stack.pop() — order matters! b was pushed after a, so b is the right operand: a OP b, not b OP a.
int(a / b) — Python's / always returns float; // is floor division (rounds toward negative infinity for negatives). LC #150 wants truncation toward zero, so int(a / b) is correct: int(-7/2) = int(-3.5) = -3, while -7 // 2 = -4.
stack.append(int(token)) — number token: push it.
return stack[0] — exactly one item remains.

Watch the RPN evaluator, frame by frame

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

token="2": push 2.  stack=[2]
token="1": push 1.  stack=[2,1]
token="+": b=1, a=2. push 2+1=3.  stack=[3]
token="3": push 3.  stack=[3,3]
token="*": b=3, a=3. push 3*3=9.  stack=[9]

return stack[0] = 9  ✅

["4","13","5","/","+"]

token="4":  push 4.   stack=[4]
token="13": push 13.  stack=[4,13]
token="5":  push 5.   stack=[4,13,5]
token="/":  b=5, a=13. int(13/5)=2. push 2. stack=[4,2]
token="+":  b=2, a=4. push 6.       stack=[6]

return 6  ✅

The actual problem — Part 2

Basic Calculator (LC #224):

Implement a basic calculator to evaluate a simple expression string. Expression may contain +, -, (, ), digits, and spaces.

"1 + 1" → 2
" 2-1 + 2 " → 3
"(1+(4+5+2)-3)+(6+8)" → 23

Infix evaluation with parentheses (number + sign stack)

Infix expressions with only + and − (no * or /) can be solved with a single stack tracking signs at each nesting level:

def calculate(s: str) -> int:
    stack  = []    # saves the running result and sign before each '('
    result = 0
    num    = 0
    sign   = 1     # +1 or -1

    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)         # build multi-digit number

        elif ch in '+-':
            result += sign * num             # flush current number
            num  = 0
            sign = 1 if ch == '+' else -1

        elif ch == '(':
            stack.append(result)             # save result before '('
            stack.append(sign)               # save sign before '('
            result = 0                       # reset for the subexpression
            sign   = 1

        elif ch == ')':
            result += sign * num             # flush number
            num     = 0
            result *= stack.pop()            # multiply by sign before '('
            result += stack.pop()            # add result before '('

        # spaces: skip (no explicit branch needed — `num` stays, nothing happens)

    result += sign * num   # flush last number
    return result

The key insight for parentheses:

When we hit (, we save the current running total and the sign in front of ( on the stack. We reset and start fresh for the subexpression. When we hit ), we finalize the subexpression result, multiply by the saved sign, and add the saved running total. This correctly handles arbitrary nesting.

Watch the infix evaluator, frame by frame

s = "(1+(4+5+2)-3)+(6+8)"

This is a long trace — let's trace the key moments:

result=0, sign=1, num=0, stack=[]

ch='(': push result(0), push sign(1). result=0, sign=1. stack=[0,1]
ch='1': num=1.
ch='+': result += 1*1=1. num=0, sign=1.
ch='(': push result(1), push sign(1). result=0, sign=1. stack=[0,1,1,1]
ch='4': num=4.
ch='+': result += 1*4=4. num=0, sign=1.
ch='5': num=5.
ch='+': result += 1*5=9. num=0, sign=1.
ch='2': num=2.
ch=')': result += 1*2=11. num=0.
        result *= stack.pop()=1 → 11.
        result += stack.pop()=1 → 12.  stack=[0,1]
ch='-': result += 0 (num=0 already flushed). sign=-1.
ch='3': num=3.
ch=')': result += -1*3=12-3=9. num=0.
        result *= stack.pop()=1 → 9.
        result += stack.pop()=0 → 9.   stack=[]
ch='+': result += 0. sign=1.
ch='(': push result(9), push sign(1). result=0, sign=1. stack=[9,1]
ch='6': num=6.
ch='+': result += 1*6=6. num=0, sign=1.
ch='8': num=8.
ch=')': result += 1*8=14. num=0.
        result *= stack.pop()=1 → 14.
        result += stack.pop()=9 → 23.  stack=[]

End: result += sign*num = 23 + 0 = 23.

return 23  ✅

Basic Calculator II: with `*` and `/` (no parentheses)

LC #227 adds multiplication and division (higher precedence than +/−). Strategy: defer +/− additions to the end by pushing signed numbers; process *// immediately.

def calculate2(s: str) -> int:
    stack, num, sign = [], 0, '+'

    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)

        if (ch in '+-*/' or i == len(s) - 1):
            if sign == '+':   stack.append(num)
            elif sign == '-': stack.append(-num)
            elif sign == '*': stack.append(stack.pop() * num)
            elif sign == '/': stack.append(int(stack.pop() / num))
            num  = 0
            sign = ch

    return sum(stack)

Why push +/- and evaluate *// immediately? Multiplication and division bind more tightly. When we see *, the previous number (at stack top) is the left operand — multiply and push back. + and - operands are accumulated in the stack and summed at the end, naturally handling left-to-right ordering.

Common traps

Watch out for these

Wrong operand order in RPN. b = stack.pop() first (right operand), then a = stack.pop() (left operand). For [3, 4, '-'], the answer is 3 - 4 = -1. If you swap: 4 - 3 = 1. Wrong.
// vs int(a/b) for truncation. Python's // floors toward negative infinity: -7 // 2 = -4. LC #150 wants truncation toward zero: int(-7/2) = int(-3.5) = -3. Always use int(a/b) for "truncate toward zero" semantics.
Forgetting to flush the last number after the loop. In the infix calculator, the last number in the string is only processed by the final result += sign * num after the loop, not inside it. Omitting this loses the last token.
Not handling multi-digit numbers. Single digit: num = int(ch). Multi-digit: num = num * 10 + int(ch). The × 10 + new_digit pattern shifts existing digits left and appends the new one.
For LC #224, forgetting negative numbers at the start. -1 + 2 starts with a -. Since sign = 1 initially and result = 0, result += sign * num when we hit + gives 0 + 1 * 0 = 0, then sign = -1, then num = 1, then at end result += -1 * 1 = -1. Total: -1. Correct — the initialization handles it naturally.

Remember this forever

RPN (postfix): push numbers, on operator pop two (b then a), push a OP b. int(a/b) not a//b.

Infix +/- with parentheses (LC #224):

digit: build num = num*10 + digit
+/-: flush result += sign*num, reset num, set sign
(: push result and sign onto stack; reset both
): flush num; result = result * stack.pop() + stack.pop()
After loop: result += sign * num

Infix with *// (LC #227): push signed numbers for +/-; immediately fold for *//; sum(stack) at end.

Check yourself

In the RPN evaluator, why must you pop `b` before `a`?

The stack is LIFO. If we push operands left-to-right, the right operand (b) was pushed last and sits on top. Popping top-first gives us b, then a. The expression is a OP b — e.g., 3 4 - = 3 - 4 = -1. If you pop a first (by reversing the pop order), you compute 4 - 3 = 1. For + and * (commutative), it doesn't matter, but for - and / it is critical.

In the LC #224 calculator, when we hit `)`, why do we multiply `result` by `stack.pop()` before adding `stack.pop()`?

When we encounter (, we push two things: (1) the running result before the (, and (2) the sign that was in front of the (. The stack is LIFO, so when we pop on ), we get sign first (most recently pushed), then result. We multiply the subexpression's result by the sign (result *= sign_before_paren) to correctly negate the entire subexpression if the sign was -1. Then we add the outer running result (result += outer_result). If we did them in the wrong order, we'd add first and then multiply — corrupting the outer result.

Practice problems

Problem	Difficulty	What to notice	Link
Evaluate Reverse Polish Notation	Medium	Pop b then a; `int(a/b)` not `a//b`	LC #150
Basic Calculator	Hard	`+`/`-` and `()`; sign stack	LC #224
Basic Calculator II	Medium	`+`/`-`/``/`/`; push signed; fold ``/`/`	LC #227
Basic Calculator III	Hard	Combines both — recursion or two stacks	LC #772
Decode String	Medium	Stack for counts and partial strings; `(` and `)`	LC #394

Next up: Stack for String Manipulation — using a stack as a character buffer to build or decode strings in one pass, covering Decode String, Remove Adjacent Duplicates, and Simplify Path.

PreviousLargest Rectangle in Histogram

Back to all topics