Stack Implementation and Parenthesis Matching

1. What is a Stack?

A stack is a linear data structure that is conceptually similar to a stack of plates or a pile of books. You can only add a new item to the top, and you can only remove an item from the top. This simple but powerful rule is known as LIFO: Last-In, First-Out. The last element you add is the first one you can take off.

Core Stack Operations

There are four primary operations associated with a stack:

• push(item): Adds an item to the top of the stack.
• pop(): Removes and returns the item from the top of thestack.
• peek() (or top()): Returns the top item without removing it.
• isEmpty(): Checks if the stack is empty.

A crucial feature of a well-implemented stack is that all these operations have a time complexity of $O(1)$. They take a constant amount of time, regardless of how many items are in the stack.

2. Implementing a Stack in Python

You can implement a stack using various underlying data structures, including the linked list we built in the last lesson. However, the most straightforward way in Python is to use its built-in list. Python's list methods append() and pop() naturally provide the LIFO behavior we need.

Here is a simple class-based implementation of a stack using a Python list:

class Stack:
    def __init__(self):
        """Initializes an empty stack."""
        self.items = []

    def push(self, item):
        """Adds an item to the top of the stack. O(1)"""
        self.items.append(item)

    def pop(self):
        """Removes and returns the top item. Returns None if the stack is empty. O(1)"""
        if not self.isEmpty():
            return self.items.pop()
        return None

    def peek(self):
        """Returns the top item without removing it. Returns None if empty. O(1)"""
        if not self.isEmpty():
            return self.items[-1]
        return None

    def isEmpty(self):
        """Checks if the stack is empty. O(1)"""
        return len(self.items) == 0

    def size(self):
        """Returns the number of items in the stack."""
        return len(self.items)

Connection to Previous Lesson:
Notice how we could also build this using our SinglyLinkedList. The push operation would correspond to insert_at_beginning(), and pop would correspond to delete_from_beginning(). Since both of those linked list operations are $O(1)$, a linked list is also a very efficient way to implement a stack.

3. Application: The Parenthesis Matching Problem

Now for the practical part. A classic use case for stacks is to check if an expression containing parentheses (), braces {}, and brackets [] is "balanced".

An expression is balanced if:

1. Every opening symbol has a corresponding closing symbol.
2. The pairs of symbols are of the same type (e.g., { is closed by }).
3. The nesting order is correct. For example, ([)] is not balanced because the ( was opened before [, but ] was closed before ).

The key insight is that the most recently opened bracket must be the first one to be closed. This "last-in, first-out" requirement is a perfect fit for a stack.

The Algorithm

As explained in the video, we can solve this with a simple algorithm:

1. Initialize an empty stack.
2. Iterate through each character of the expression string from left to right.
3. If the character is an opening bracket ((, {, or [), push it onto the stack.
4. If the character is a closing bracket (), }, or ]):
   a. Check if the stack is empty. If it is, the expression is unbalanced because there's a closing bracket with no opener. Return False.
   b. If the stack is not empty, pop the top element.
   c. Compare the popped bracket with the current closing bracket. If they don't form a matching pair (e.g., ( and )), the expression is unbalanced. Return False.
5. After the loop finishes, check if the stack is empty. If it is, every opening bracket found a matching closer, so the expression is balanced. If the stack is not empty, there are unmatched opening brackets, so it's unbalanced.

4. Implementing the Solution in Python

Now, let's translate this algorithm into a Python function using the stack principles we've learned.

Here's a breakdown of the logic you saw in the article, with some added comments for clarity.

def is_balanced(expression):
    # Our stack will store the opening brackets
    stack = []
    
    # A mapping to easily check for matching pairs
    matching_bracket = {')': '(', ']': '[', '}': '{'}
    
    for char in expression:
        # If it's an opening bracket, push it onto the stack
        if char in "({[":
            stack.push(char)
        # If it's a closing bracket
        elif char in ")}]":
            # Case 1: Stack is empty, so no matching opener
            if not stack:
                return False
            
            # Pop the last opened bracket
            top_element = stack.pop()
            
            # Case 2: Popped bracket doesn't match the current closer
            if matching_bracket[char] != top_element:
                return False
                
    # Case 3: After loop, stack must be empty for expression to be balanced
    return not stack

# --- Let's test it ---
expr1 = "()[]{}"  # Balanced
expr2 = "([)]"    # Not Balanced
expr3 = "{{[[(())]]}}" # Balanced
expr4 = "((("      # Not Balanced

print(f"'{expr1}' is balanced: {is_balanced(expr1)}")
print(f"'{expr2}' is balanced: {is_balanced(expr2)}")
print(f"'{expr3}' is balanced: {is_balanced(expr3)}")
print(f"'{expr4}' is balanced: {is_balanced(expr4)}")

Notice that we've simply used a Python list (stack = []) as our stack. stack.append() is our push and stack.pop() is our pop. The line return not stack is a concise way of writing return len(stack) == 0.

Conclusion

In this lesson, you've added another essential data structure to your toolkit. The stack, with its simple LIFO principle, is incredibly versatile and forms the backbone of many algorithms related to parsing, backtracking, and managing execution flow (like function calls in a program).

Key Takeaways:

• A stack is a Last-In, First-Out (LIFO) data structure.
• The primary operations are push, pop, peek, and isEmpty, all of which operate in $O(1)$ time.
• Stacks can be implemented using arrays/lists or linked lists.
• The parenthesis matching problem is a classic example that demonstrates the power of stacks for handling nested structures. The core logic is to push opening brackets and pop to verify closing ones.

Preview of the Next Lesson:

Having mastered the LIFO principle of stacks, we will next explore its counterpart: the queue. A queue operates on a First-In, First-Out (FIFO) principle, just like a checkout line at a store. We will implement a queue and see how it's used to model different kinds of real-world processes.