5 Best Ways to Check for Balanced Brackets in Python

Rate this post

πŸ’‘ Problem Formulation: Ensuring brackets are balanced and well-formed in strings is a common requirement in programming, particularly when parsing or analyzing code. A valid string must have each opening bracket (e.g., (, [, or {) closed by a bracket of the same type in the correct order. For instance, the input "( [ { } ] )" is balanced, while "( [ } )" is not.

Method 1: Using a Stack

This method involves iterating over each character in the string and pushing opening brackets onto a stack. When a closing bracket is encountered, the method checks if the stack’s top corresponds to the closing bracket type. If it matches, the bracket is popped; otherwise, the string is unbalanced.

Here’s an example:

def is_balanced_brackets(s):
    stack = []
    brackets_map = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in brackets_map.values():
            stack.append(char)
        elif char in brackets_map.keys():
            if not stack or stack[-1] != brackets_map[char]:
                return False
            stack.pop()
    return not stack

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

Output: True

This code snippet defines the function is_balanced_brackets() that returns True if the input string of brackets is balanced. It uses a stack to keep track of opening brackets and a map for the relation between closing and opening brackets, making sure each closing bracket has a corresponding opening bracket.

Method 2: Recursive Reduction

This method employs a recursive function that eliminates matching pairs of brackets until there are no more pairs to remove or an imbalance is detected. It is a direct approach that applies the basic rules of balanced brackets.

Here’s an example:

def reduce_brackets(s):
    pairs = ["()", "{}", "[]"]
    while any(pair in s for pair in pairs):
        for pair in pairs:
            s = s.replace(pair, "")
    return not s

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

Output: True

The reduce_brackets() function iteratively removes pairs of brackets until no more pairs are present. If the final string is empty, the brackets are balanced. This approach is straightforward but can be inefficient for long strings as it re-scans the string multiple times.

Method 3: Regex Pattern Matching

This method uses regular expressions to identify and eliminate pairs of brackets, leveraging the Python re module. It’s a more advanced technique that can potentially be more efficient than the recursive reduction.

Here’s an example:

import re

def is_balanced_brackets_regex(s):
    while True:
        s_new = re.sub(r'(\(\)|\[\]|\{\})', '', s)
        if s_new == s:
            break
        s = s_new
    return not s

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

Output: True

This code example defines a function is_balanced_brackets_regex() that uses a loop and a regex pattern to repeatedly remove matching pairs of brackets. It stops when no changes are made to the input string, and returns True if the string is empty at the end.

Method 4: Iterative State Machine

This method sets up a state machine that changes states based on the current and next characters in the string. It’s a more complex approach that can be very fast and elegant for specific use cases.

Here’s an example:

def is_balanced_state_machine(s):
    state, i, n = [], 0, len(s)
    brackets_map = {')': '(', '}': '{', ']': '['}
    while i < n:
        if s[i] in brackets_map.values():
            state.append(s[i])
        elif s[i] in brackets_map and (not state or state.pop() != brackets_map[s[i]]):
            return False
        i += 1
    return not state

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

Output: True

In is_balanced_state_machine(), the state is represented as a stack, and the function iterates through the string with an index, closely resembling a finite state machine. The stack and look-up map are used to check the balance of brackets as it processes the string character by character.

Bonus One-Liner Method 5: List Comprehension

This one-liner approach uses list comprehension to create a stack, pushing and popping brackets, all within a single line of code. It is a condensed version of the stack method.

Here’s an example:

is_balanced_one_liner = lambda s: not [c for b in s for c in (b if b in "{[(" else [], ')' if b == '(' else ']' if b == '[' else '}' if b == '{' else '') if c != b][::2] 

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

Output: True

The is_balanced_one_liner() is a lambda function that leverages a complex list comprehension for its logic. The list comprehension manages a virtual stack and checks for balance by attempting to pair each closing bracket with a recent opening bracket, if it fails to find a match the brackets are unbalanced.

Summary/Discussion

  • Method 1: Using a Stack. Reliable and easy to understand. Might not be the most efficient for extremely long strings.
  • Method 2: Recursive Reduction. Simplistic and easy to implement. Very inefficient for long strings due to repeated string scanning.
  • Method 3: Regex Pattern Matching. More efficient than recursive reduction. Can be overkill for simple cases and is less readable.
  • Method 4: Iterative State Machine. Efficient and elegant. More complex to understand and implement correctly.
  • Method 5: List Comprehension One-Liner. Extremely compact. Can be difficult to read and understand due to its compactness.