Balanced Parenthesis Problem using Stack

Balanced Parenthesis Problem

The balanced parenthesis problem involves checking if every opening parenthesis in an expression has a corresponding closing parenthesis and if they are correctly nested. This can be efficiently solved using a stack, which follows the Last In, First Out (LIFO) principle.

---

Step-by-Step Process

Consider an expression containing parentheses:

"(a + b) * (c + d)"

To check if the parentheses are balanced, follow these steps:

1. Initialize an Empty Stack: Use a stack to keep track of opening parentheses.
2. Traverse the Expression: Iterate through each character in the expression.
3. Push Opening Parentheses: If an opening parenthesis is encountered, push it onto the stack.
4. Check Closing Parentheses: If a closing parenthesis is encountered, check if the stack is empty (which would indicate an unmatched closing parenthesis) or if the top of the stack has a matching opening parenthesis. If it matches, pop the stack; otherwise, the parentheses are not balanced.
5. Final Stack Check: After traversing the expression, check if the stack is empty. If it is, the parentheses are balanced; otherwise, they are not.

---

Pseudo Code

Function is_balanced(expression):
    # Initialize an empty stack
    stack = []
    # Define matching parentheses pairs
    pairs = {')': '(', ']': '[', '}': '{'}
    # Traverse the expression
    For char in expression:
        # If it's an opening parenthesis, push to stack
        If char in '({[':
            stack.append(char)
        # If it's a closing parenthesis, check for matches
        Elif char in ')}]':
            If not stack or stack[-1] != pairs[char]:
                Return False
            stack.pop()
    # Final stack check
    Return len(stack) == 0

---

Python Program to Solve the Balanced Parenthesis Problem

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        return len(self.stack) == 0

    def traverse(self):
        for item in reversed(self.stack):
            print(item, end=" -> ")
        print("None")

# Function to check for balanced parentheses
def is_balanced(expression):
    stack = Stack()
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in expression:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False
    return stack.is_empty()

# Example usage:
expressions = ["(a + b) * (c + d)", "(a + b] * {c + d)", "{[a + b] * (c + d)}"]
for expr in expressions:
    result = is_balanced(expr)
    print(f"Expression: {expr} -> Balanced: {result}")

This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and traversing the stack. The is_balanced function uses the stack to check if the parentheses in an expression are balanced by pushing opening parentheses onto the stack and popping them when matching closing parentheses are encountered. The function returns True if the parentheses are balanced and False otherwise.