Case Study 1: Building a Bracket Matcher

Using a Stack to Validate Code Syntax

Every time you save a Python file in VS Code, something remarkable happens in milliseconds: the editor scans your entire file for syntax issues, including mismatched brackets, parentheses, and braces. If you forget a closing parenthesis or accidentally type } where you meant ], a red squiggly line appears instantly. The algorithm behind this is one of the most elegant applications of a stack in computer science.

In this case study, we'll build a bracket matcher from scratch, starting with the simplest possible version and progressively making it more robust — the same way production software is developed.

The Problem

Given a string of code, determine whether all brackets ((), [], {}) are properly matched. "Properly matched" means:

1. Every opening bracket has a corresponding closing bracket of the same type.
2. Brackets are closed in the correct order (you can't close a [ with }).
3. No closing bracket appears without a matching opener.

Examples:

Why a Stack?

The key insight is that brackets nest. When you see ([{}]), the innermost brackets must be closed first. The most recently opened bracket is the first one that should be closed — that's LIFO behavior. A stack naturally tracks this.

Think of it like Russian nesting dolls. You open them from the outside in, but you close them from the inside out. The last doll you opened is the first one you close.

Version 1: Parentheses Only

Let's start with the simplest case — matching only ( and ):

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)


def check_parens(text: str) -> bool:
    """Check if parentheses are balanced."""
    stack = Stack()

    for ch in text:
        if ch == "(":
            stack.push(ch)
        elif ch == ")":
            if stack.is_empty():
                return False    # closing without opening
            stack.pop()

    return stack.is_empty()     # all openers must be closed


# Tests
print(check_parens("()"))          # True
print(check_parens("(())"))        # True
print(check_parens("((())())"))    # True
print(check_parens("(()"))         # False — unclosed (
print(check_parens("())"))         # False — extra )
print(check_parens(")("))          # False — closer before opener

How it works: - Scan left to right. - ( → push onto the stack (we'll need to match it later). - ) → pop the stack (we're matching the most recent (). - If we try to pop an empty stack, there's an unmatched ). - After scanning, if the stack isn't empty, there are unmatched (s.

The algorithm is O(n) time and O(n) space in the worst case (when every character is an opening bracket).

Version 2: All Three Bracket Types

Now let's handle (), [], and {}:

def check_brackets_v2(text: str) -> bool:
    """Check if all bracket types are properly matched."""
    MATCH = {")": "(", "]": "[", "}": "{"}
    stack = Stack()

    for ch in text:
        if ch in "([{":
            stack.push(ch)
        elif ch in ")]}":
            if stack.is_empty():
                return False
            top = stack.pop()
            if top != MATCH[ch]:
                return False    # type mismatch

    return stack.is_empty()


# Tests
print(check_brackets_v2("{[()]}"))       # True
print(check_brackets_v2("([)]"))         # False — mismatched nesting
print(check_brackets_v2("{[](){}[]}"))   # True
print(check_brackets_v2("["))            # False — unclosed

The MATCH dictionary maps each closing bracket to its expected opening bracket. When we pop the stack, we verify that the popped opener matches the closer we just encountered. If they don't match, the brackets are incorrectly nested.

Version 3: Detailed Error Messages

A production bracket checker doesn't just say "invalid" — it tells you where and why:

def check_brackets_v3(text: str) -> tuple[bool, str]:
    """
    Check brackets with detailed error messages.
    Returns (is_valid, message).
    """
    OPENERS = "([{"
    CLOSERS = ")]}"
    MATCH = {")": "(", "]": "[", "}": "{"}
    NAMES = {"(": "parenthesis", ")": "parenthesis",
             "[": "square bracket", "]": "square bracket",
             "{": "curly brace", "}": "curly brace"}

    stack = Stack()

    for i, ch in enumerate(text):
        if ch in OPENERS:
            stack.push((ch, i))             # store character AND position
        elif ch in CLOSERS:
            if stack.is_empty():
                return (False,
                    f"Unexpected closing {NAMES[ch]} '{ch}' "
                    f"at position {i} with no matching opener")
            top_char, top_pos = stack.pop()
            if top_char != MATCH[ch]:
                return (False,
                    f"Mismatched {NAMES[top_char]} '{top_char}' "
                    f"at position {top_pos} with "
                    f"{NAMES[ch]} '{ch}' at position {i}")

    if not stack.is_empty():
        unclosed_char, unclosed_pos = stack.pop()
        remaining = stack.size()
        msg = (f"Unclosed {NAMES[unclosed_char]} '{unclosed_char}' "
               f"at position {unclosed_pos}")
        if remaining > 0:
            msg += f" (and {remaining} more unclosed bracket(s))"
        return False, msg

    return True, "All brackets matched correctly!"


# Demonstrate error messages
test_cases = [
    "print(data[0])",                     # Valid
    "result = func(a, b",                 # Unclosed (
    "data = [1, 2, 3}",                   # Mismatched [ with }
    ")(",                                 # Closer before opener
    "if (x > 0) and [y < (10])",          # Mismatched ( with ]
    "f(g(h({x: [1, 2, 3]})))",            # Valid (deeply nested)
]

for text in test_cases:
    valid, message = check_brackets_v3(text)
    status = "VALID" if valid else "ERROR"
    print(f"[{status}] '{text}'")
    print(f"         {message}")
    print()

# Expected output:
# [VALID] 'print(data[0])'
#          All brackets matched correctly!
#
# [ERROR] 'result = func(a, b'
#          Unclosed parenthesis '(' at position 13
#
# [ERROR] 'data = [1, 2, 3}'
#          Mismatched square bracket '[' at position 7 with curly brace '}' at position 15
#
# [ERROR] ')('
#          Unexpected closing parenthesis ')' at position 0 with no matching opener
#
# [ERROR] 'if (x > 0) and [y < (10])'
#          Mismatched parenthesis '(' at position 20 with square bracket ']' at position 23
#
# [VALID] 'f(g(h({x: [1, 2, 3]})))'
#          All brackets matched correctly!

Version 4: Handling Strings and Comments

Real code has strings and comments that might contain brackets. The bracket ( inside "print(" shouldn't count as an opener. A production matcher needs to skip these regions:

def check_brackets_v4(text: str) -> tuple[bool, str]:
    """
    Check brackets, ignoring those inside string literals
    and comments.
    """
    MATCH = {")": "(", "]": "[", "}": "{"}
    stack = Stack()
    in_string = False
    string_char = ""
    in_comment = False

    for i, ch in enumerate(text):
        # Handle comments (# to end of line)
        if ch == "#" and not in_string:
            in_comment = True
            continue
        if ch == "\n":
            in_comment = False
            continue
        if in_comment:
            continue

        # Handle string literals
        if ch in ('"', "'") and not in_string:
            in_string = True
            string_char = ch
            continue
        if in_string and ch == string_char:
            in_string = False
            continue
        if in_string:
            continue

        # Normal bracket processing
        if ch in "([{":
            stack.push((ch, i))
        elif ch in ")]}":
            if stack.is_empty():
                return False, (f"Unmatched '{ch}' at position {i}")
            top_char, top_pos = stack.pop()
            if top_char != MATCH[ch]:
                return False, (
                    f"Mismatched '{top_char}' at position "
                    f"{top_pos} with '{ch}' at position {i}")

    if not stack.is_empty():
        top_char, top_pos = stack.pop()
        return False, f"Unclosed '{top_char}' at position {top_pos}"

    return True, "All brackets matched!"


# Tests with strings and comments
print(check_brackets_v4('text = "Hello (world)"'))  # Valid — ( ) inside string
# (True, 'All brackets matched!')

print(check_brackets_v4('x = 5  # note: (not a bracket'))  # Valid — ( in comment
# (True, 'All brackets matched!')

print(check_brackets_v4("data = [1, 2, 3]  # list)\n"))  # Valid — ) in comment
# (True, 'All brackets matched!')

Performance Analysis

For a 10,000-line Python file with moderate nesting (depth ~20), the stack never holds more than about 20 elements. The algorithm is extremely efficient.

What We Learned

1. Stacks naturally model nested structures. Any time you have "the last thing opened must be the first thing closed," think stack.

2. Start simple, add complexity. Version 1 handled only (). Version 2 added bracket types. Version 3 added error messages. Version 4 handled strings and comments. Each version built on the last.

3. Store context, not just values. By pushing (character, position) tuples instead of just characters, we got precise error messages for free.

4. Edge cases matter. The empty stack check catches ) without a matching (. The post-loop stack check catches ( without a matching ). Missing either one leaves a class of bugs undetected.

5. Real-world tools use this exact algorithm. VS Code, PyCharm, Vim, and every code editor implement bracket matching with a stack. The production versions are more sophisticated (handling multi-line strings, escape characters, regex literals), but the core algorithm is identical to what you've seen here.

Try It Yourself

1. Extend Version 4 to handle triple-quoted strings (""" and ''').
2. Add support for angle brackets (<>) used in HTML/XML.
3. Modify the checker to report all errors, not just the first one. (Hint: after finding an error, you need to decide how to continue scanning. One approach: skip the mismatched closer and keep going.)
4. Build a simple REPL that reads Python-like expressions and validates brackets in real time.