Python Program to Check Balanced Parentheses

Checks whether every bracket in a string is closed in the right order, using a list as a stack of the brackets still open.

Brackets are balanced when every opening bracket is closed by one of the same kind, in the reverse order they were opened: the last one opened is the first one closed. {[()()]} is balanced. ([)] isn't: the ) arrives while the [ is still open. Code editors and Python itself make this check every time they read code.

The tool for the job is a stack, a pile where items are only added to and taken from the top. A Python list works as one: append() adds to the end and pop() takes from it.

Program

def is_balanced(text):
    """True if every bracket closes in the right order."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)
        elif char in pairs:
            # It has to close the last bracket still open
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack  # True only if nothing is left open


print("{[()()]}:", is_balanced("{[()()]}"))
print("([)]:", is_balanced("([)]"))

Open in the editor Download balanced_brackets.py

Output

{[()()]}: True
([)]: False

How it works

Visualize Step through the program line by line: each step below shows up as its line runs.

1. pairs is a dictionary from each closing bracket to the opening bracket it closes.
2. stack holds the brackets that are open and not yet closed, the most recent at the end.
3. The loop goes through the text one character at a time. An opening bracket goes on top of the stack.
4. A closing bracket has to close the last bracket still open, the one on top of the stack. If the stack is empty, there's nothing for it to close; if pop() takes off a different kind, the brackets cross. Either way the text isn't balanced. Because or stops at the first part that's true, pop() runs only when the stack has something in it. Any other character, such as a letter or a space, is skipped.
5. At the end, every bracket that was opened must have been closed, so the stack must be empty. not stack is True for an empty list.
6. The program checks {[()()]}, which is balanced, and ([)], which isn't.

Checking {[()()]} (the top of the stack is on the right):

And ([)]:

Time and space complexity

The loop looks at each of the n characters once. Adding to or taking from the end of a list takes the same short time however long the list is, and looking a character up in pairs or in "([{" is quick too, as each holds only three brackets. So the check is O(n). In the worst case, a text of opening brackets only, every character goes on the stack, so the extra space is O(n).

Other ways to write it

With a counter, for one kind of bracket

When the text has only ( and ), a number can stand in for the stack: add 1 for each (, take 1 for each ), and fail if it ever drops below 0. It needs O(1) space, but it can't see that ([)] is wrong, so it works for one kind of bracket only.

def is_balanced(text):
    depth = 0
    for char in text:
        if char == "(":
            depth += 1
        elif char == ")":
            depth -= 1
            if depth < 0:
                return False
    return depth == 0

print(is_balanced("(()())"), is_balanced("())("))

By removing pairs

A balanced string of brackets always has a pair with nothing between its brackets, such as (). Removing those pairs until nothing changes leaves an empty string only when the brackets were balanced. It's short, but it works only on text made of brackets, and it can take O(n²) time.

def is_balanced(brackets):
    before = None
    while brackets != before:
        before = brackets
        for pair in ("()", "[]", "{}"):
            brackets = brackets.replace(pair, "")
    return brackets == ""

print(is_balanced("{[()()]}"), is_balanced("([)]"))

Try it yourself

• Check "(]", "((", "))" and the empty string "". Which are balanced, and which line decides each one?
• Check a line of code, such as "print(len([1, 2]))": the letters, digits and spaces are skipped.
• Add angle brackets: ">": "<" in pairs, and < with the other opening brackets.
• Return the position of the first closing bracket that doesn't fit instead of False, with enumerate(text).

More data structures programs

• Python Program to Implement a Queue Beginner
• Python Program to Implement a Binary Search Tree Intermediate
• Python Program for Inorder, Preorder and Postorder Traversal Intermediate
• Python Program to Implement a Linked List Intermediate
• Python Program for Prefix Sums and Range Sum Queries Intermediate
• Python Program to Find the Maximum Sum of K Consecutive Elements Intermediate
• Python Program to Find the K Largest Elements Using a Heap Intermediate