Valid Parentheses

Stacks & Queues: lesson 2 of 5

A closing bracket must answer the newest opening one.

Lesson 2 of 5 · 5 min

Step 1 of 14

verdictscanning

scanning "{[()]}"

{

[

(

)

]

}

stackempty

Every opening bracket goes on the stack. A closing one must answer the most recently opened.

The Idea

Push every opening bracket. When a closing bracket shows up, it has to match the one on top — the most recently opened. Anything else means the string is broken. One pass, O(n), and valid input finishes with an empty stack.

Real-World Example

A code editor checking your markup as you type. Close a </section> while a <div> is still open and the line lights up straight away, because the tag you close must be the last one you opened, not just any tag still hanging around.

The Code

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)              # remember this opening
        elif not stack or stack.pop() != pairs[ch]:
            return False                  # wrong or missing partner
    return not stack                      # leftovers mean unclosed

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

Your turn

Put the steps in the right order.

Return True only if the stack ended up empty
Start with an empty stack
Push every opening bracket onto the stack
On a closing bracket, pop the top and compare partners

Mini quiz

1 / 3

Valid Parentheses