Stack-Based Parsing: Parentheses, Decode String & Calculator

Stacks are the natural tool for any problem involving nested structures — parentheses, brackets, HTML tags, or recursive patterns. The core idea is always the same: opening symbols are pushed, closing symbols pop and validate. Let’s master every variant of this pattern.

Pattern 1: Valid Parentheses

Given a string containing (, ), {, }, [, ], determine if the input is valid.

Valid: Every open bracket has a matching close bracket in the correct order.

def is_valid(s):
    """
    Check if parentheses are balanced.
    Time: O(n), Space: O(n)
    """
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in matching:
            # Closing bracket — check if it matches the top
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
        else:
            # Opening bracket — push
            stack.append(char)

    return len(stack) == 0  # Stack must be empty


print(is_valid("()[]{}"))    # True
print(is_valid("{[()]}"))    # True
print(is_valid("([)]"))      # False — mismatched nesting
print(is_valid("(("))         # False — unclosed
print(is_valid(""))           # True — empty is valid

Alternative: Push the expected closer

def is_valid_v2(s):
    """Push the expected closing bracket instead."""
    stack = []
    openers = {'(': ')', '[': ']', '{': '}'}

    for char in s:
        if char in openers:
            stack.append(openers[char])  # Push expected closer
        elif not stack or stack.pop() != char:
            return False

    return len(stack) == 0

This version is slightly cleaner — when you see a closer, you just check if it matches the top.

Pattern 2: Minimum Removals to Make Valid

Given a string with parentheses and other characters, find the minimum number of parentheses to remove to make it valid.

def min_remove_to_make_valid(s):
    """
    Remove minimum parentheses to make string valid.
    Return the resulting string.
    Time: O(n), Space: O(n)
    """
    s = list(s)  # Convert to list for mutation
    stack = []   # Stack of indices of unmatched '('

    # Pass 1: Mark unmatched ')' and track unmatched '('
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()  # Matched
            else:
                s[i] = ''    # Unmatched ')' — remove

    # Pass 2: Remove remaining unmatched '('
    for i in stack:
        s[i] = ''

    return ''.join(s)


print(min_remove_to_make_valid("lee(t(c)o)de)"))  # "lee(t(c)o)de"
print(min_remove_to_make_valid("a)b(c)d"))         # "ab(c)d"
print(min_remove_to_make_valid("))(("))             # ""

Count-only version

If you just need the count, not the resulting string:

def min_removals_count(s):
    """Count minimum removals needed."""
    open_count = 0   # Unmatched (
    close_count = 0  # Unmatched )

    for char in s:
        if char == '(':
            open_count += 1
        elif char == ')':
            if open_count > 0:
                open_count -= 1
            else:
                close_count += 1

    return open_count + close_count


print(min_removals_count("(()))"))  # 1
print(min_removals_count(")("))     # 2

Pattern 3: Longest Valid Parentheses

Find the length of the longest valid (well-formed) parentheses substring.

def longest_valid_parentheses(s):
    """
    Find length of longest valid parentheses substring.
    Time: O(n), Space: O(n)
    """
    stack = [-1]  # Stack of indices; -1 is boundary marker
    max_len = 0

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:  # ')'
            stack.pop()
            if not stack:
                # No matching '(' — push current index as new boundary
                stack.append(i)
            else:
                # Valid pair found — length = current index - top of stack
                max_len = max(max_len, i - stack[-1])

    return max_len


print(longest_valid_parentheses("(()"))      # 2
print(longest_valid_parentheses(")()())"))    # 4
print(longest_valid_parentheses("()(()"))     # 2
print(longest_valid_parentheses("(()())"))    # 6

Why start with -1?

The -1 serves as a boundary marker. When we see ) and pop, the new top tells us where the current valid sequence started. If the stack becomes empty (no matching (), we push the current index as the new boundary.

Alternative: Two-pass O(1) space

def longest_valid_parentheses_o1(s):
    """O(1) space using two passes."""
    max_len = 0

    # Left to right
    open_count = close_count = 0
    for char in s:
        if char == '(':
            open_count += 1
        else:
            close_count += 1
        if open_count == close_count:
            max_len = max(max_len, 2 * close_count)
        elif close_count > open_count:
            open_count = close_count = 0

    # Right to left (handles cases like "(()")
    open_count = close_count = 0
    for char in reversed(s):
        if char == '(':
            open_count += 1
        else:
            close_count += 1
        if open_count == close_count:
            max_len = max(max_len, 2 * open_count)
        elif open_count > close_count:
            open_count = close_count = 0

    return max_len

Pattern 4: Decode String

Given an encoded string like "3[a2[c]]", decode it to "accaccacc".

Rules:

• k[encoded_string] means repeat encoded_string k times
• Brackets can be nested

def decode_string(s):
    """
    Decode string with nested brackets.
    Time: O(n * max_k), Space: O(n)
    """
    stack = []
    current_string = ""
    current_num = 0

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            # Save current state and start fresh
            stack.append((current_string, current_num))
            current_string = ""
            current_num = 0
        elif char == ']':
            # Pop previous state and repeat current string
            prev_string, num = stack.pop()
            current_string = prev_string + current_string * num
        else:
            current_string += char

    return current_string


print(decode_string("3[a]2[bc]"))      # "aaabcbc"
print(decode_string("3[a2[c]]"))       # "accaccacc"
print(decode_string("2[abc]3[cd]ef"))  # "abcabccdcdcdef"
print(decode_string("100[ha]"))        # "ha" repeated 100 times

How the stack works for 3[a2[c]]

Char | current_string | current_num | stack
-----|----------------|-------------|------
3    | ""             | 3           | []
[    | ""             | 0           | [("", 3)]
a    | "a"            | 0           | [("", 3)]
2    | "a"            | 2           | [("", 3)]
[    | ""             | 0           | [("", 3), ("a", 2)]
c    | "c"            | 0           | [("", 3), ("a", 2)]
]    | "a" + "c"*2 = "acc" | 0     | [("", 3)]
]    | "" + "acc"*3 = "accaccacc" | 0 | []

Pattern 5: Basic Calculator

Evaluate a string expression with +, -, parentheses, and spaces.

def basic_calculator(s):
    """
    Evaluate expression with +, -, (, ).
    Time: O(n), Space: O(n)
    """
    stack = []
    result = 0
    num = 0
    sign = 1  # 1 for +, -1 for -

    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char == '+':
            result += sign * num
            num = 0
            sign = 1
        elif char == '-':
            result += sign * num
            num = 0
            sign = -1
        elif char == '(':
            # Save current result and sign, start fresh
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif char == ')':
            result += sign * num
            num = 0
            result *= stack.pop()  # Pop sign
            result += stack.pop()  # Pop previous result

    result += sign * num  # Don't forget the last number
    return result


print(basic_calculator("1 + 1"))            # 2
print(basic_calculator("2 - 1 + 2"))        # 3
print(basic_calculator("(1+(4+5+2)-3)+(6+8)"))  # 23
print(basic_calculator("-(3+2)+5"))          # 0

Extended: Calculator with *, /

def calculator_with_multiply(s):
    """
    Evaluate expression with +, -, *, / (no parentheses).
    Time: O(n), Space: O(n)
    """
    stack = []
    num = 0
    sign = '+'  # Previous operator

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

        if (char in '+-*/' or i == len(s) - 1) and char != ' ':
            if sign == '+':
                stack.append(num)
            elif sign == '-':
                stack.append(-num)
            elif sign == '*':
                stack.append(stack.pop() * num)
            elif sign == '/':
                # Python integer division truncates toward negative infinity
                # Use int() to truncate toward zero (as in most languages)
                stack.append(int(stack.pop() / num))

            sign = char
            num = 0

    return sum(stack)


print(calculator_with_multiply("3+2*2"))    # 7
print(calculator_with_multiply("3/2"))      # 1
print(calculator_with_multiply("3+5/2"))    # 5

The General Stack-Parsing Mental Model

All stack-parsing problems follow this pattern:

def stack_parse_template(s):
    """
    General template for stack-based parsing.
    """
    stack = []

    for char in s:
        if is_opener(char):
            # Save current state
            stack.append(current_state)
            reset_state()
        elif is_closer(char):
            # Restore previous state and combine
            prev_state = stack.pop()
            combine(prev_state, current_state)
        else:
            # Process character normally
            update_state(char)

    return final_result()

The key decision at each character:

1. Opening delimiter ((, [, digit before [): Push current context, start new scope
2. Closing delimiter (), ]): Pop context, merge with current scope
3. Regular character: Accumulate in current scope

Generate Valid Parentheses

A bonus problem — generate all valid combinations of n pairs:

def generate_parentheses(n):
    """
    Generate all valid combinations of n pairs of parentheses.
    Time: O(4^n / sqrt(n)), Space: O(n)  — Catalan number
    """
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return

        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)

        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)

    backtrack("", 0, 0)
    return result


print(generate_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

Complexity Summary

Problem	Time	Space
Valid Parentheses	O(n)	O(n)
Minimum Removals	O(n)	O(n)
Longest Valid	O(n)	O(n) or O(1)
Decode String	O(n * max_k)	O(n)
Basic Calculator	O(n)	O(n)
Generate Parentheses	O(4^n/sqrt(n))	O(n)

Practice Problems

1. LeetCode 20 — Valid Parentheses: The fundamental problem (Easy)
2. LeetCode 1249 — Minimum Remove to Make Valid: Remove invalid brackets (Medium)
3. LeetCode 32 — Longest Valid Parentheses: Longest valid substring (Hard)
4. LeetCode 394 — Decode String: Nested bracket decoding (Medium)
5. LeetCode 224 — Basic Calculator: +, -, parentheses (Hard)
6. LeetCode 227 — Basic Calculator II: +, -, *, / without parentheses (Medium)
7. LeetCode 22 — Generate Parentheses: Backtracking generation (Medium)
8. LeetCode 856 — Score of Parentheses: Scoring nested parentheses (Medium)

Key Takeaways

• The stack-parsing pattern: push on open, pop on close, accumulate otherwise.
• Use index-based stacks when you need to track positions (longest valid, minimum removals).
• For calculators: handle precedence by processing * and / immediately (push result), but defer + and - (push the number).
• Decode String shows how the stack preserves “context” at each nesting level — the same pattern used in compilers and interpreters.
• All these problems are O(n) time because each character is processed once, and each stack operation is O(1).