Check whether a string of brackets is valid.

How to think about it

This is the problem interviewers use to check whether you reach for a stack on reflex. The tell is in the word “valid”: a closing bracket must match the most recently opened one still waiting — last in, first out. The moment you hear “match the thing I opened most recently,” your hand should already be moving toward a stack, and saying that out loud is half the points.

The mechanism is small. Keep a stack of unmatched openers. Walk the string one character at a time. See an opener — (, [, { — and push it. See a closer and ask two questions: is the stack empty, or does its top fail to match this closer? Either way the string is broken, so return False. Otherwise pop the matched opener and move on. When the loop ends, the string is valid only if the stack is empty — anything left over is an opener nobody closed. A tiny dict mapping each closer to its opener keeps the matching honest.

A worked example

def is_valid(s):
    stack = []
    match = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)                       # opener -> remember it
        else:
            if not stack or stack[-1] != match[ch]:  # guard BEFORE indexing
                return False
            stack.pop()                            # matched -> discharge it
    return len(stack) == 0                          # nothing left unclosed?

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

# Trace the stack on a nested case
def is_valid_verbose(s):
    stack = []
    match = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != match[ch]:
                print(f"  ch={ch!r}  -> mismatch, return False")
                return False
            stack.pop()
        print(f"  ch={ch!r}  stack={stack}")
    return len(stack) == 0

print("Trace for '{[]}':")
print("result:", is_valid_verbose("{[]}"))

True
False
True
False
True
Trace for '{[]}':
  ch='{'  stack=['{']
  ch='['  stack=['{', '[']
  ch=']'  stack=['{']
  ch='}'  stack=[]
result: True

Two lines in the output earn their keep. "([)]" returns False because when the ) arrives the stack top is [, not ( — correct nesting is violated even though the bracket counts balance. And "(" returns False not inside the loop but at the very end: every iteration passed, yet the stack still holds one opener, so the final emptiness check is what catches it. The trace of "{[]}" shows the stack growing to ['{', '['] and then draining back to empty, which is exactly the shape of a valid string.