Stack-Based Expression Evaluation: How to Parse and Compute in Coding Interviews

Why this pattern matters in interviews

Stack-based expression evaluation shows up in a lot of interview problems because it tests a few core skills at once: parsing, state management, and disciplined use of a stack. If you can handle parentheses, operator precedence, and nested structure, you can solve a surprising number of problems without reaching for heavy parsing machinery.

The good news is that most of these problems follow the same idea: read the input left to right, push what you need to remember, and resolve subexpressions when you hit a boundary such as ) or the end of the string.

That makes this pattern worth learning well. Once it clicks, problems like valid parentheses, basic calculators, and expression scoring become much easier to reason about.

Problem statement

Expression evaluation problems usually ask you to do one of these:

• Validate whether a string has balanced brackets or parentheses
• Evaluate a math expression with +, -, *, /
• Handle nested parentheses correctly
• Respect operator precedence
• Sometimes support unary signs like -2 or -(3+4)

The exact rules vary, but the underlying challenge is the same: the expression is linear text, while the meaning is hierarchical. Stacks help bridge that gap.

Common examples

• "()[]{}" → valid parentheses check
• "1 + 1" → evaluate to 2
• "(1+(4+5+2)-3)+(6+8)" → evaluate to 23
• "2*(3+4)" → evaluate to 14

Intuition and insight

A stack is a natural fit whenever you need to remember context until something closes.

Think about this expression:

1 + (2 - (3 + 4))

When you enter the first parenthesis, you need to remember the running total and the current sign. When you enter the nested parenthesis, you need to remember the new context again. When you close a parenthesis, you pop the previous context and combine it with the result you just computed.

That is the central idea:

• Push state when you enter a nested scope
• Pop state when you exit it
• Accumulate values as you scan characters

For valid parentheses, the stack stores opening brackets. For calculators, the stack often stores partial results and signs.

There are a few broad variants of this pattern:

1. Bracket matching: keep track of open symbols and verify proper closing order
2. Basic calculator without multiplication/division: maintain a running result and sign
3. Full calculator with precedence: use a stack to defer addition/subtraction and collapse multiplication/division immediately

Approach 1: Valid parentheses with a stack

This is the simplest version and a good warm-up. When you see an opening bracket, push it. When you see a closing bracket, check whether the top of the stack matches.

Python code

def is_valid_parentheses(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)

    return not stack

Walkthrough example

Input:

"({[]})"

Step by step:

• Read ( → push (
• Read { → push {
• Read [ → push [
• Read ] → top matches [ → pop
• Read } → top matches { → pop
• Read ) → top matches ( → pop
• Stack is empty → valid

If you try "([)]", the stack catches the mismatch when ) appears while [ is on top.

Why it works

The stack preserves the order of unmatched opening brackets. Since closing brackets must match the most recent unmatched opener, a stack is exactly the right data structure.

Approach 2: Basic calculator with +, -, and parentheses

Now let’s evaluate an arithmetic expression like:

(1 + (4 + 5 + 2) - 3) + (6 + 8)

This version usually allows +, -, spaces, digits, and parentheses. No multiplication or division yet.

Core idea

You only need four pieces of state:

• result: current accumulated value in the current scope
• sign: the sign to apply to the next number
• num: the number currently being built from digits
• stack: stores the previous result and sign when you enter parentheses

When you encounter (, you save the current context:

• push result
• push sign
• reset result and sign for the inner expression

When you encounter ), you finish the current number, then collapse the inner result into the outer context.

Python code

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    num = 0

    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in '+-':
            result += sign * num
            num = 0
            sign = 1 if ch == '+' else -1
        elif ch == '(':
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif ch == ')':
            result += sign * num
            num = 0
            result *= stack.pop()   # sign before '(' 
            result += stack.pop()   # result before '('

    result += sign * num
    return result

Worked example 1

Input:

"1 + (4 + 5 + 2) - 3"

Let’s trace the key state:

Final answer: 10

Why it works

This approach avoids building a parse tree. Instead, it evaluates on the fly while preserving enough context for nested parentheses. The stack stores only what you need to resume the outer expression after finishing an inner one.

Approach 3: Calculator with +, -, *, /

Once multiplication and division enter the picture, operator precedence matters.

A common stack strategy is:

• Push signed numbers for + and -
• On * or /, pop the last number, combine it immediately, then push the result back
• At the end, sum the stack

This works because * and / bind tighter than + and -, so you can resolve them right away.

Python code

def calculate_basic(s: str) -> int:
    stack = []
    num = 0
    sign = '+'
    s += '+'  # sentinel to flush the last number

    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == ' ':
            continue
        else:
            if sign == '+':
                stack.append(num)
            elif sign == '-':
                stack.append(-num)
            elif sign == '*':
                stack[-1] *= num
            elif sign == '/':
                # truncate toward zero
                stack[-1] = int(stack[-1] / num)

            sign = ch
            num = 0

    return sum(stack)

Worked example 2

Input:

"3+2*2"

Trace:

• Read 3, then + → push 3
• Read 2, then * → push 2
• Read 2, then end sentinel + → resolve * with previous top: 2 * 2 = 4
• Stack becomes [3, 4]
• Sum = 7

If you evaluated strictly left to right without precedence, you would get (3+2)*2 = 10, which is wrong.

Worked example 3

Input:

" 14-3/2 "

Trace:

• 14 then - → push 14
• 3 then / → push -3
• 2 then end → resolve /: -3 / 2 = -1 in truncation-toward-zero arithmetic
• Stack = [14, -1]
• Sum = 13

Be careful with division rules. In interview problems, division often truncates toward zero, which is different from Python’s // for negative numbers. Using int(a / b) gives the usual interview behavior.

Complexity analysis

All of these stack-based solutions are linear in the length of the input because you process each character once.

Practical note

Space can be lower in some cases if you optimize for only one type of parentheses or simplify input assumptions, but in interview settings, O(n) space is the standard and acceptable answer.

How to recognize this pattern in an interview

Use a stack-based expression approach when you see any of these clues:

• You need to match opening and closing symbols
• The input has nested structure
• You must evaluate something while scanning left to right
• Operator precedence or scope changes the meaning of a token
• You need to recover the previous state after finishing a subexpression

Key takeaways

• A stack is ideal for nested structure and last-in-first-out context recovery
• For parentheses validation, the stack stores opening brackets
• For calculators, the stack stores partial results or saved contexts
• Parse digits carefully; multi-digit numbers are a common source of bugs
• Pay attention to spaces, unary signs, and division behavior

Common pitfalls

• Forgetting to flush the last number at the end of the string
• Mishandling multi-digit numbers by treating each digit separately
• Not resetting num after applying an operator
• Confusing the meaning of - as subtraction versus unary negation
• Using // for division when the problem expects truncation toward zero

Related problems

Once you understand this pattern, these problems become good practice:

• Valid Parentheses
• Min Stack
• Basic Calculator
• Basic Calculator II
• Basic Calculator III
• Evaluate Reverse Polish Notation
• Score of Parentheses
• Decode String

A lot of these are the same idea in different clothing: preserve context, resolve when you have enough information, and use the stack to manage nested structure.

If you’d like to see the variables update live as you step through, check out codebrew.ai.

Practice these next

1. Valid Parentheses — confirm matching pairs with a stack
2. Basic Calculator — evaluate +, -, and parentheses
3. Basic Calculator II — handle +, -, *, and /
4. Score of Parentheses — compute nested score values
5. Decode String — expand patterns like 3[a2[c]]

The main skill here is not memorizing one solution. It’s learning to see when an expression needs a stack to preserve context. Once you can do that, a large class of interview questions becomes much more manageable.