Stack Applications: Parentheses Balancing

1. Defining the "Balanced Parentheses" Problem

First, what does it mean for parentheses (and brackets, and braces) to be "balanced"? It's more than just having an equal number of opening and closing symbols. There are specific rules that must be followed.

A string of brackets is considered balanced if:

1. Every opening bracket has a corresponding closing bracket of the same type. For example, ( must be closed by ), not ].
2. Brackets are closed in the correct order. The most recently opened bracket must be the first one to be closed.

Let's look at some examples.

To solidify this definition, let's watch a short video that breaks down these rules with clear examples.

2. Developing an Algorithm with a Stack

How can we programmatically check for these rules? A first thought might be to just count the number of opening and closing brackets of each type. However, as the table above shows with ([)], this isn't enough. The order is crucial.

Consider the string {[()]}. As we scan from left to right, notice the pattern of how brackets are closed:

• The ( is opened.
• The ) is closed. It matches the most recent opening bracket, (.
• The [ is opened.
• The ] is closed. It matches the most recent unclosed opening bracket, [.
• The { is opened.
• The } is closed. It matches the most recent unclosed opening bracket, {.

This pattern—"the last one opened is the first one closed"—is exactly the LIFO behavior of a stack. This gives us a powerful clue for our algorithm.

Let's watch a video that builds this algorithm from the ground up.

To summarize the algorithm:

1. Create an empty stack.
2. Iterate through the string one character at a time.
3. If the character is an opening bracket ((, {, [), push it onto the stack.
4. If the character is a closing bracket (), }, ]):
   a. Check if the stack is empty. If it is, there's no matching opener, so the string is unbalanced.
   b. If the stack is not empty, pop the top element. If this popped element is not the corresponding opening bracket for the current closing bracket, the string is unbalanced.
5. After the loop finishes, if the stack is empty, it means every opening bracket found its match. The string is balanced!
6. If the stack is not empty, it means there are leftover opening brackets that were never closed. The string is unbalanced.

This image provides a great visual trace of this process.

3. Implementing the Solution in Python

Now, let's translate this algorithm into Python code. We'll use a list as our stack, just as you learned in the previous lesson. A dictionary will also be very helpful to map closing brackets to their opening counterparts, making the matching logic clean and easy to read.

This video demonstrates a concise and effective Python implementation.

Here is a complete, commented function based on the logic from the video.

def is_balanced(expression):
    """
    Checks if a string of brackets is balanced using a stack.
    """



    # The stack will store the opening brackets we encounter.
    stack = []




    # A dictionary to map closing brackets to their opening counterparts.
    # This makes checking for a match very efficient.
    pairs = {')': '(', '}': '{', ']': '['}




    # Iterate through each character in the expression string.
    for char in expression:



        # If the character is an opening bracket, push it onto the stack.
        # We can check this by seeing if it's in the *values* of our pairs dict.
        if char in pairs.values():
            stack.append(char)
        



        # If the character is a closing bracket...
        elif char in pairs.keys():



            # The string is unbalanced if:
            # 1. The stack is empty (a closing bracket with no opener before it).
            # 2. The opener we pop from the stack doesn't match the current closer.
            if not stack or stack.pop() != pairs[char]:
                return False
        



        # We simply ignore any other characters that are not brackets.




    # After the loop, the string is balanced only if the stack is empty.
    # An empty stack means every opener found a matching closer.
    return not stack # `not []` is True; `not ['(', ...]` is False

4. Your Turn: Trace the Execution

Reading code is one thing; seeing it in action is another. To truly understand how it works, trace the is_balanced function with the following inputs. On a piece of paper or in a text editor, keep track of the stack's state after processing each character.

1. Input: "{[()]}" (should return True)
2. Input: "{[(])}" (should return False)

Let's do the first character of the second example together to get you started:

• Input: "{[(])}"
• char is {. This is an opening bracket (in pairs.values()).
• Action: stack.append('{').
• Stack state: ['{']

Now, continue this process for the rest of the characters in both strings. See if your final result matches the expected output and try to pinpoint exactly where the logic fails for the unbalanced string. This exercise is crucial for building the problem-solving intuition needed for interviews.

Conclusion

Congratulations! You've successfully used a stack to solve a non-trivial algorithmic problem. This exercise demonstrates how choosing the right data structure can turn a complex-sounding problem into a straightforward and elegant solution.

Key Takeaways:

• The balanced parentheses problem requires checking for both correct type and correct order of brackets.
• The stack's LIFO (Last-In, First-Out) property is perfect for this task because the most recently opened bracket must be the first to be closed.
• The algorithm is: push opening brackets, and when you see a closing bracket, pop and check for a match.
• An empty stack at the end signifies a balanced string; a non-empty stack signifies an unbalanced one.
• Using a dictionary to map closing to opening brackets makes the implementation clean and efficient.

Preview of the Next Lesson:

We've now seen how the LIFO principle of stacks is useful. But what if we need the opposite behavior? In the next lesson, we will explore the queue data structure, which operates on a FIFO (First-In, First-Out) principle. You'll learn what a queue is and how to implement one in Python using the collections.deque object.