5 Best Ways to Check Whether Parentheses are Balanced or Not in Python

by

💡 Problem Formulation: This article focuses on how to verify the balancing of parentheses in a given string using Python. Imbalanced parentheses are common programming errors that could lead to bugs in code execution, especially in languages where they dictate logical groupings and block structures. The task is to create a function that takes a string as an input, such as "((3^2 + 8)*(5/2))/(2+6)", and returns True if the parentheses are balanced and False otherwise.

Method 1: Using Stack

An efficient method to check for balanced parentheses is to use a stack. As each opening parenthesis is encountered, it’s pushed onto the stack. When a closing parenthesis is found, the stack is popped. If the stack is empty or the types don’t match (e.g., closing a square bracket when expecting a curly brace), the parentheses are not balanced.

Here’s an example:

def is_balanced(input_string):
    stack = []
    parentheses_map = {')': '(', '}': '{', ']': '['}
    
    for char in input_string:
        if char in parentheses_map.values():
            stack.append(char)
        elif char in parentheses_map.keys():
            if stack == [] or parentheses_map[char] != stack.pop():
                return False
    return stack == []

print(is_balanced("((3^2 + 8)*(5/2))/(2+6)"))

Output: True

This function iterates over each character in the string, adding opening parentheses to the stack and popping the stack for each closing parenthesis. If the stack is empty before popping or the types of parentheses don’t match, it returns False. Otherwise, it returns True if the stack is empty after all characters have been processed, indicating balanced parentheses.

Method 2: Recursive Approach

Another approach is the recursive removal of each innermost pair of parentheses. If the resulting string has no parentheses, they were balanced; otherwise, not. This method is less efficient for long strings but is an interesting algorithmic variant.

Here’s an example:

def is_balanced_recursive(input_string):
    if not input_string:
        return True
    if '()' in input_string:
        return is_balanced_recursive(input_string.replace('()', ''))
    return False

print(is_balanced_recursive("((3^2 + 8)*(5/2))/(2+6)"))

Output: True

The function is_balanced_recursive calls itself, each time reducing the input string by removing the innermost pair of parentheses. This continues until either there are no more parentheses to remove (indicating balance) or no such pair can be found (indicating imbalance).

Method 3: Using Regular Expressions

Regular expressions can simplify the recursive approach by using pattern matching to repeatedly find and remove inner parenthesis pairs until no more pairs can be found or until there are mismatched parentheses.

Here’s an example:

import re

def is_balanced_regex(input_string):
    while '()' in input_string or '{}' in input_string or '[]' in input_string:
        input_string = re.sub(r'\(\)|\[\]|\{\}', '', input_string)
    return not re.search(r'[\(\)\[\]\{\}]', input_string)

print(is_balanced_regex("((3^2 + 8)*(5/2))/(2+6)"))

Output: True

The function is_balanced_regex uses the re.sub method from Python’s regular expressions module to strip out pairs of matching parentheses. If the search finds any remaining parentheses after this process, it means the string had imbalanced parentheses.

Method 4: Count Matching

This method counts the number of each type of parenthesis. If for every type the counts of the openings and closings are equal, the parentheses are balanced. This quick method fails with nested structures, but works for simple cases where nesting doesn’t occur.

Here’s an example:

def is_balanced_count(input_string):
    return input_string.count('(') == input_string.count(')') and \
           input_string.count('{') == input_string.count('}') and \
           input_string.count('[') == input_string.count(']')

print(is_balanced_count("((3^2 + 8)*(5/2))/(2+6)"))

Output: True

The function is_balanced_count simply uses count method for each type of parenthesis to check if the numbers of open and close parentheses are the same. It fails to detect balanced parentheses with incorrect nesting, such as "(]".

Bonus One-Liner Method 5: Lambda Function

For enthusiasts who love concise code, a one-liner using a lambda function and a filter can check for balanced parentheses. This is more of a curiosity and not recommended for production code due to reduced readability.

Here’s an example:

is_balanced_lambda = lambda s, _=None: len(s) == 0 if not _ else is_balanced_lambda(filter(lambda x: x != _+1, s), s.find('(') + 1 or None)
print(is_balanced_lambda(list("((3^2 + 8)*(5/2))/(2+6)")))

Output: True

This lambda starts by converting the input into a list of characters and recursively filters out pairs of matching parentheses until none are left or a pair can’t be filtered, which signals imbalance.

Summary/Discussion

  • Method 1: Stack Approach. Highly efficient and canonical solution for balanced parentheses. Handles complex and nested structures well. Requires extra space for the stack.
  • Method 2: Recursive Approach. Conceptually simple, but inefficient for long strings due to multiple replacements. Does not scale well with deeply nested structures.
  • Method 3: Using Regular Expressions. Easier to read and suitable for simple cases. However, regex can be slower and less efficient than stack-based approaches for very long strings.
  • Method 4: Count Matching. Quick and direct for non-nested parentheses. Fails if parentheses are correctly matching in number but nested incorrectly.
  • Bonus Method 5: Lambda Function. A clever one-liner showing the power of Python’s lambda and filter functions, but lacking the clarity necessary for most use cases.