Balanced brackets with a stack: 5 tested examples in Python

If an exam or interview asks you to check a string like ({[]}), a stack solves it in one pass. Every output below comes from a real run on Python 3.10.

The core idea

Scan left to right. Push every opening bracket on a stack. On a closing bracket, pop and check that it matches. Only two things can go wrong: the closing bracket does not match the top of the stack, or openings are left over at the end.

Example 1: the checker

def is_valid(s):
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pair[ch]:
                return False
    return stack == []

print(is_valid("({[]})"))
print(is_valid("(]"))
print(is_valid("([)]"))
print(is_valid("((("))
print(is_valid(""))

Output:

True
False
False
False
True

An empty string is balanced: nothing is left unmatched.

Example 2: watch "([)]" fail

Counting brackets is not enough. This string has one of each, and it is still wrong:

def trace(s):
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []
    for i, ch in enumerate(s):
        if ch in '([{':
            stack.append(ch)
            print(f"step {i}: push {ch}  stack={stack}")
        else:
            if not stack or stack[-1] != pair[ch]:
                print(f"step {i}: '{ch}' needs '{pair[ch]}' on top, stack={stack} -> FAIL")
                return
            stack.pop()
            print(f"step {i}: pop  {ch}  stack={stack}")
    print("balanced" if not stack else f"unclosed left: {stack}")

trace("([)]")

Output:

step 0: push (  stack=['(']
step 1: push [  stack=['(', '[']
step 2: ')' needs '(' on top, stack=['(', '['] -> FAIL

The ) needs ( on top, but [ is in the way. The stack catches the order, not just the count.

Example 3: minimum brackets to add

For strings with only round brackets, count instead of using a real stack:

def min_adds(s):
    opens = adds = 0
    for ch in s:
        if ch == '(':
            opens += 1
        elif opens:
            opens -= 1
        else:
            adds += 1
    return opens + adds

print(min_adds("())"))
print(min_adds("((("))
print(min_adds("()))(("))

Output:

1
3
4

Example 4: minimum removals to fix a string

Track indices, then drop every bracket that never matched:

def min_removals(s):
    stack = []          # indices of '(' waiting for a match
    drop = set()        # indices to remove
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()
            else:
                drop.add(i)
    drop.update(stack)  # '(' that never matched
    return ''.join(ch for i, ch in enumerate(s) if i not in drop)

print(repr(min_removals("a)b(c)d")))
print(repr(min_removals("(a(b)c")))
print(repr(min_removals(")(")))

Output:

'ab(c)d'
'a(b)c'
''

Example 5: longest valid substring

A classic interview follow-up. Keep the index before the current valid run at the bottom of the stack:

def longest_valid(s):
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if stack:
                best = max(best, i - stack[-1])
            else:
                stack.append(i)
    return best

print(longest_valid("(()"))
print(longest_valid(")()())"))
print(longest_valid(""))

Output:

2
4
0

When to reach for a stack

• Any "is this nested correctly" question: brackets, tags, undo history, function calls.
• Counting alone never works: ([)] has equal counts and is still wrong.
• One pass is enough: every example here is O(n) time and O(n) worst-case space.

More stack practice (postfix evaluation, circular queues) in DSA in 30 Days, Episode 4: https://techvaniai.blogspot.com/2026/10/dsa-04-stack-postfix-evaluation-circular-queue.html

Python docs on using lists as stacks: https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks