Balanced Parenthesis Problem in Python

Understanding Balanced Parenthesis Problem

The balanced parenthesis problem involves checking whether a given string of brackets is balanced or not.

We will explore three different methods to solve this problem in Python.

Method 1: Using Stack

def is_balanced(expr):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for ch in expr:
        if ch in mapping.values():
            stack.append(ch)
        elif ch in mapping.keys():
            if not stack or stack.pop() != mapping[ch]:
                return False
    return not stack

expr = "{[()]}"
print("Balanced" if is_balanced(expr) else "Not Balanced")
            

Method 2: Using Counter

def is_balanced(expr):
    count = 0
    for ch in expr:
        if ch == '(':
            count += 1
        elif ch == ')':
            count -= 1
        if count < 0:
            return False
    return count == 0

expr = "(())"
print("Balanced" if is_balanced(expr) else "Not Balanced")
            

Method 3: Recursion

def check_balance(expr, index=0, count=0):
    if count < 0:
        return False
    if index == len(expr):
        return count == 0
    if expr[index] == '(':
        return check_balance(expr, index + 1, count + 1)
    if expr[index] == ')':
        return check_balance(expr, index + 1, count - 1)
    return check_balance(expr, index + 1, count)

expr = "((()))"
print("Balanced" if check_balance(expr) else "Not Balanced")