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

Question

How can you determine if a string contains balanced parentheses? Please provide a detailed explanation of your approach using Python, including any necessary code examples.

To determine if a string contains balanced parentheses, you can use a stack data structure. The concept of balanced parentheses means that each opening parenthesis '(' has a corresponding closing parenthesis ')' and they are properly nested. Here's a detailed explanation of the approach along with a Python code example:

1. **Initialize a Stack**: Use a list to simulate a stack in Python, which will help keep track of opening parentheses.

2. **Traverse the String**: Iterate over each character in the string.

3. **Push Opening Parentheses**: If the character is an opening parenthesis '(', push it onto the stack.

4. **Match Closing Parentheses**: If the character is a closing parenthesis ')':
   - Check if the stack is empty. If it is, this means there's no matching opening parenthesis, and the string is unbalanced.
   - If the stack is not empty, pop the top element from the stack, which should be the matching opening parenthesis.

5. **Check the Stack**: After processing all characters in the string, check if the stack is empty. If it is empty, this means all opening parentheses had matching closing ones, and the string is balanced. If not, the string is unbalanced.

Here's a Python code example implementing this approach:

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

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

# If the stack is empty, all parentheses are balanced
    return len(stack) == 0

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

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

In this code:
- We define a function `is_balanced_parentheses` that takes a string `s` as input.
- A stack is used to keep track of opening parentheses.
- As we iterate through the string, we handle each parenthesis accordingly.
- Finally, we check if the stack is empty to determine if the parentheses in the string are balanced.

This solution efficiently checks for balanced parentheses with a time complexity of O(n), where n is the length of the string, since each character is processed once.

Accepted Answer

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:

```python
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.

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

Question Explain

Answer Example

Related Interview Questions