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