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.
Consider an expression containing parentheses:
"(a + b) * (c + d)"
To check if the parentheses are balanced, follow these steps:
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
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.