How can you use Python to check if a string has balanced parentheses?

To determine if a string contains balanced parentheses, you can indeed use a stack data structure. This approach is effective because it leverages the Last-In-First-Out (LIFO) principle of stacks to ensure each opening parenthesis '(' properly pairs with a closing parenthesis ')'. Here is a detailed breakdown of the procedure along with a Python code implementation:

Approach:

1. Initialize a Stack: Use a list to simulate a stack in Python to keep track of opening parentheses.

2. Traverse the String: Loop through each character in the string to determine if it is an opening or closing parenthesis.

3. Push Opening Parentheses: For each opening parenthesis '(', push it onto the stack.

4. Match Closing Parentheses:

   • If a closing parenthesis ')' is encountered, check if the stack is empty. An empty stack at this point indicates there's no corresponding opening parenthesis, thus unbalancing the string.
   • If the stack isn't empty, pop the top element (the last added opening parenthesis) from the stack, indicating a matched pair.

5. Check for Balance: After processing all characters, verify that the stack is empty. An empty stack suggests all opening parentheses were successfully matched with closing ones, signifying a balanced string. Otherwise, the string is unbalanced.

Python Implementation:

def is_balanced_parentheses(s):
    # Initialize a stack to track opening parentheses
    stack = []

    # Traverse each character in the string
    for char in s:
        # If it's an opening parenthesis, push it to the stack
        if char == '(':
            stack.append(char)
        # If it's a closing parenthesis
        elif char == ')':
            # Return False if stack is empty (unbalanced condition)
            if not stack:
                return False
            # Pop from stack for a matched pair
            stack.pop()

    # Check if the stack is empty at the end
    return len(stack) == 0

# Example usage
string1 = "(a + b) * (c + d)"
string2 = "(a + b)) * (c + d"
string3 = "((a + b) * (c + d))"

print(is_balanced_parentheses(string1))  # Output: True
print(is_balanced_parentheses(string2))  # Output: False
print(is_balanced_parentheses(string3))  # Output: True

Explanation of the Code:

• Function Definition: The function is_balanced_parentheses checks for balanced parentheses in a string s.
• Stack Usage: A list acts as a stack, utilizing methods like append() for pushing and pop() for removing elements.
• Character Iteration: Each character is examined to determine if it's an opening or closing parenthesis, adjusting the stack accordingly.
• Balance Check: Successively popping from the stack for matching parentheses ensures correct nesting and pairing, indexed by an empty stack at the function's conclusion.

Time Complexity:

• The function operates in O(n) time complexity, where n is the length of the string, because it traverses the string once and performs constant time operations for each character.

This implementation provides a robust solution for checking balanced parentheses using Python, efficiently handling all standard cases of balanced and unbalanced configurations.