DocsHub
PythonAdvanced

Valid Parentheses

Learn how to check if brackets are correctly opened and closed using a stack in Python.

Valid Parentheses

Problem

Given a string containing brackets (, ), {, }, [, ], check if the brackets are valid. A string is valid when:

  • Every opening bracket has a matching closing bracket
  • Brackets are closed in the correct order — most recently opened closes first
Input:  "()"
Output: True

Input:  "()[]{}"
Output: True

Input:  "(]"
Output: False

Input:  "([)]"
Output: False

Input:  "{[]}"
Output: True

Input:  "((("
Output: False

Logic

A stack is the perfect data structure for this problem. It works like a stack of plates — you can only add or remove from the top.

  1. Loop through each character
  2. If it is an opening bracket (, [, { — push it onto the stack
  3. If it is a closing bracket ), ], } — check if the top of the stack has the matching opening bracket
  4. If it matches — pop it off the stack
  5. If it does not match — invalid
  6. At the end — if the stack is empty, all brackets were matched — valid
  7. If the stack is not empty — some brackets were never closed — invalid

Flow

Yes No — closing bracket Yes No Yes No Yes No Yes No Start stack = empty list Take each character Opening bracket?( or and or curly open Push onto stack Stack is empty? Return Falsenothing to match Top of stack matches? Pop from stack Return Falsewrong bracket More characters? Stack empty? Return True Return Falseunclosed brackets

Solution 1 — using a stack

The standard approach. Use a list as a stack — append() to push, pop() to remove.

def is_valid(s):
    stack = []

    # map each closing bracket to its matching opening bracket
    matching = {
        ")": "(",
        "]": "[",
        "}": "{"
    }

    for char in s:
        if char in "([{":
            # opening bracket — push onto stack
            stack.append(char)

        elif char in ")]}":
            # closing bracket — check if stack has matching opener
            if not stack:
                return False   # nothing to match

            top = stack[-1]   # peek at top of stack

            if top == matching[char]:
                stack.pop()   # match found — remove from stack
            else:
                return False  # wrong bracket on top

    # valid only if all brackets were matched
    return len(stack) == 0


print(is_valid("()"))       # True
print(is_valid("()[]{}"))   # True
print(is_valid("(]"))       # False
print(is_valid("([)]"))     # False
print(is_valid("{[]}"))     # True
print(is_valid("((("))      # False
print(is_valid(""))         # True — empty string is valid

Code Execution — Solution 1

Trace through is_valid("{[]}"):

StepcharActionstack
Start——[]
1st{Opening → push["{"]
2nd[Opening → push["{", "["]
3rd]Closing → top is [, matches ] → pop["{"]
4th}Closing → top is {, matches } → pop[]
End—Stack empty → True[]

Trace through is_valid("([)]"):

StepcharActionstack
Start——[]
1st(Opening → push["("]
2nd[Opening → push["(", "["]
3rd)Closing → top is [, does NOT match ) which needs (Return False

The [ was opened after ( but ) tried to close before ] — wrong order.

Trace through is_valid("(((")

StepcharActionstack
1st(Push["("]
2nd(Push["(", "("]
3rd(Push["(", "(", "("]
End—Stack NOT empty → False["(", "(", "("]

Three opening brackets were never closed.

stack[-1] peeks at the top of the stack without removing it. This is how you check what is on top before deciding to pop. In Python a list works perfectly as a stack — append() adds to the top, pop() removes from the top, and [-1] peeks at the top.

Solution 2 — cleaner with pop default

Instead of peeking first, pop directly and use a default value for empty stack.

def is_valid(s):
    stack = []

    matching = {
        ")": "(",
        "]": "[",
        "}": "{"
    }

    for char in s:
        if char in matching:
            # closing bracket
            # pop from stack — use "#" as default if stack is empty
            top = stack.pop() if stack else "#"

            if matching[char] != top:
                return False
        else:
            # opening bracket — push
            stack.append(char)

    return not stack   # True if stack is empty


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

Code Execution — Solution 2

Trace through is_valid("(]"):

Stepcharchar in matching?top = stack.pop()matching[char]Match?stack
1st(No → push———["("]
2nd]Yestop = "("matching["]"] = "[""[" != "(" → return False

Solution 3 — using replace

Repeatedly remove valid pairs (), [], {} until nothing changes. If the string becomes empty — valid.

def is_valid(s):
    previous = None

    # keep removing matched pairs until no more changes
    while s != previous:
        previous = s
        s = s.replace("()", "")
        s = s.replace("[]", "")
        s = s.replace("{}", "")

    # valid if nothing remains
    return s == ""


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

Code Execution — Solution 3

Trace through is_valid("{[]}"):

Passs beforeAfter removing []After removing {}s after
1st"{[]}""{}"""""
2nd""""""""

s == previous on pass 2 → stop. s == "" → return True

Trace through is_valid("([)]"):

Passs beforeAfter removing ()After removing []s after
1st"([)]""([)]" (no () adjacent)"([)]" (no [] adjacent)"([)]"
2nd"([)]"samesame"([)]"

s == previous → stop. s != "" → return False

Solution 3 is clever but much slower — it repeatedly scans the whole string. For deeply nested brackets like ((((((())))))), it makes many passes. The stack solution is always O(n) — one pass. Use Solution 1 or 2 in real code.

Solution 4 — extended: also check content

A real-world extension — validate brackets in a code string that contains other characters too.

def is_valid_code(s):
    """
    Check brackets in a string that may contain
    letters, numbers, and other characters.
    Only brackets are validated.
    """
    stack = []

    matching = {")": "(", "]": "[", "}": "{"}
    opening = set("([{")
    closing = set(")]}")

    for char in s:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
        # all other characters are ignored

    return len(stack) == 0


# code-like strings
print(is_valid_code("if (x > 0) { return [1, 2]; }"))   # True
print(is_valid_code("def func(a, b): return {a: b}"))    # True
print(is_valid_code("arr[0) = 5"))                       # False
print(is_valid_code("x = (1 + [2 * 3])"))               # True

Code Execution — Solution 4

Trace through is_valid_code("arr[0) = 5"):

Only tracking bracket characters: [, 0, ) → only [ and ) matter (ignore 0, spaces, =, 5)

StepcharTypeActionstack
[[OpeningPush["["]
))Closingmatching[")"] = "(", top is "[" → mismatch → False

[ was opened but ) tried to close — wrong bracket type.

Which solution to use?

SolutionHowBest when
Solution 1Stack with peekMost readable — default choice
Solution 2Stack with pop defaultSlightly more concise
Solution 3Replace pairsClever but avoid for large inputs
Solution 4Stack ignoring non-bracketsReal code validation

Output

True
True
False
False
True
False
True

True
True
False
True

Two Sum

Learn how to find two numbers in a list that add up to a target value in Python.

Longest Word

Learn how to find the longest word in a sentence in Python.

On this page

Valid ParenthesesProblemLogicFlowSolution 1 — using a stackCode Execution — Solution 1Solution 2 — cleaner with pop defaultCode Execution — Solution 2Solution 3 — using replaceCode Execution — Solution 3Solution 4 — extended: also check contentCode Execution — Solution 4Which solution to use?Output