Stacking Up: Balancing Parentheses Using a Stack for Coding Interviews

Introduction

Balancing parentheses is a classic problem often seen in coding interviews. The task is to determine whether a given string of parentheses is balanced. The problem can extend to other types of brackets, such as curly braces {} and square brackets []. In this blog post, we'll explore a straightforward solution to this problem using a stack data structure in Python.

Understanding Stacks

A stack is a Last-In-First-Out (LIFO) data structure. In Python, a list can be used as a stack where we can use the append() method for push operation and pop() method for pop operation.

stack = []
stack.append('a')  # push 'a' onto the stack
stack.append('b')  # push 'b' onto the stack
print(stack.pop())  # pop and print the top of the stack: 'b'

Balancing Parentheses Using a Stack

We can use a stack to balance parentheses. The algorithm is as follows:

1. Initialize a new empty stack.
2. Traverse the given string from left to right.
3. If the current character is an opening parenthesis (, push it onto the stack.
4. If the current character is a closing parenthesis ), check if the stack is empty. If it is, the string is not balanced. If it's not empty, pop the top element from the stack.
5. After the traversal, if the stack is empty, the string is balanced; otherwise, it's not.

Here's how it looks in Python:

def is_balanced(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0

Extending to Other Types of Brackets

The above algorithm can easily be extended to handle other types of brackets. We just need to push the closing bracket onto the stack whenever we see an opening bracket, and then check if the top of the stack matches the current character for each closing bracket.

def is_balanced(s):
    stack = []
    brackets = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in brackets.values():  # Opening bracket.
            stack.append(brackets[char])
        elif char in brackets.keys():  # Closing bracket.
            if not stack or stack.pop() != char:
                return False
    return len(stack) == 0

Conclusion

Balancing parentheses is a common coding interview problem that tests your understanding of stack data structures. It's a great example of how stacks can be used to solve problems involving matching pairs or maintaining a certain order. Remember, the more you practice, the better you'll become at identifying when and how to use these fundamental data structures in your solutions. Happy coding!

P.S. Want weekly python coding challenges and news? Sign up for the newsletter to get them directly in your inbox: https://weeklypython.substack.com/welcome