Valid Parentheses

1. The Problem

Given a string containing only (, ), {, }, [, ] — determine if the string is valid. A string is valid when:

• Every open bracket has a matching close bracket of the same type
• Brackets close in the correct order (innermost first)

# "()"       → True
# "()[]{}"   → True
# "(]"       → False  (wrong type)
# "([)]"     → False  (wrong order)
# "{[]}"     → True
# ""         → True   (empty is valid)

2. Why a Stack?

Brackets nest. The most recently opened bracket must be the next one closed. That "last in, first out" behavior is exactly what a stack provides.

# As you read  { [ ( ) ] }
#
# See {  → push  stack: ['{']
# See [  → push  stack: ['{', '[']
# See (  → push  stack: ['{', '[', '(']
# See )  → top is '(' — matches! pop.  stack: ['{', '[']
# See ]  → top is '[' — matches! pop.  stack: ['{']
# See }  → top is '{' — matches! pop.  stack: []
# Empty stack = valid!

A counter-based approach (just count opens vs closes) fails on "([)]" — the counts balance but the order is wrong. Only a stack tracks the order.

3. The Solution

def is_valid(s):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

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

    return not stack  # Valid only if nothing is left unmatched

print(is_valid("()[]{}"))  # True
print(is_valid("([)]"))    # False
print(is_valid("{[]}"))    # True

4. Step-by-Step Trace

Tracing "({[]})":

Stack is empty at the end → True.

5. Edge Cases

print(is_valid(""))      # True  — empty string
print(is_valid("["))      # False — unclosed bracket
print(is_valid("]"))      # False — close with empty stack
print(is_valid("(]"))     # False — wrong type