Balancing Act: Solving the Balanced Brackets Problem in Python

Introduction

In coding interviews and competitive programming, one common problem is checking if a string of brackets is balanced. Balanced brackets mean every opening bracket has a corresponding closing bracket in the correct order. This problem is not just a theoretical exercise; it has practical applications in validating code syntax, expressions in calculators, and even in some text editors.

Today, we’ll break down a Python function, isBalanced(s), that determines if a string containing brackets is balanced. Let’s dive into the code, understand the problem it solves, and explain each part step-by-step.

The Problem

Given a string s consisting solely of characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, the goal is to determine if the brackets are balanced. A balanced string means:

Every opening bracket has a corresponding closing bracket.
The brackets close in the correct order.

For example:

s = "{[()]}" is balanced.
s = "{[(])}" is not balanced.

The Solution

Here is the Python function to solve this problem:

def isBalanced(s):
    stack = []
    bracket_pairs = {
        '}': '{',
        ')': '(',
        ']': '['
    }

    for char in s:
        if char in bracket_pairs.values():  # Opening bracket
            stack.append(char)
        elif char in bracket_pairs.keys():  # Closing bracket
            if stack and stack[-1] == bracket_pairs[char]:
                stack.pop()
            else:
                return "NO"

    return "YES" if not stack else "NO"

Let’s break down the function to understand how it works.

Step-by-Step Explanation

Initialize the Stack:
```
stack = []
```
We use a list as a stack to keep track of the opening brackets. A stack follows the Last In, First Out (LIFO) principle, which is ideal for this type of problem.
Define Bracket Pairs:
```
bracket_pairs = {
    '}': '{',
    ')': '(',
    ']': '['
}
```
We use a dictionary to map each closing bracket to its corresponding opening bracket. This will help us check if the brackets match correctly.
Iterate Through the String:
```
for char in s:
```
We loop through each character in the input string s.
Check for Opening Brackets:
```
if char in bracket_pairs.values():  # Opening bracket
    stack.append(char)
```
If the character is an opening bracket (one of the values in our dictionary), we push it onto the stack.
Check for Closing Brackets:
```
elif char in bracket_pairs.keys():  # Closing bracket
    if stack and stack[-1] == bracket_pairs[char]:
        stack.pop()
    else:
        return "NO"
```
If the character is a closing bracket (one of the keys in our dictionary), we need to check if it matches the last opening bracket on the stack.
- If the stack is not empty and the last item on the stack matches the corresponding opening bracket from our dictionary, we pop the stack.
- If the stack is empty or the brackets do not match, we return “NO” immediately because the string is not balanced.
Final Check:
```
return "YES" if not stack else "NO"
```
After processing all characters, we check if the stack is empty. If it is empty, all opening brackets had matching closing brackets in the correct order, so we return “YES”. Otherwise, we return “NO”.

Conclusion

The isBalanced function efficiently checks if a string of brackets is balanced using a stack. This method ensures that every opening bracket has a corresponding closing bracket and that they are in the correct order.

By understanding and implementing this function, you can solve a common problem encountered in coding interviews and improve your knowledge of data structures like stacks and dictionaries. Whether you’re parsing code, validating expressions, or building a text editor, this fundamental algorithm is a valuable tool in your programming toolkit.