Stack

Introduction

Take a look at full implementation of Stack

Stack is a Last In, First Out (LIFO) data structure, which is widely used in many computer science applications such as function call management, expression parsing, and more. It follows the principle that the last item added is the first one to be removed.

A good analogy is a pile of books. If we want to retrieve a book from this stack, we can only take the book on top. Taking a book from the bottom is precarious and we don’t want to topple the entire stack. Therefore, we’ll take down the top book on the stack and read it or do whatever we want with it.

Stack Operations

• Push: The operation to insert elements in a stack is called push. Push adds the element in the last place, so the new element automatically becomes the top.
• Pop: Popping is when we take the top book of the stack and put it down. Deletes the most recently added item.
• Peek: “What’s the top element?” and it can give that to us using the peek operation. Note that the peek operation does not remove the top element, it merely returns it.

Implementation of Stack

class Stack():
    def __init__(self):
        self.items = []

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

    def push(self, item):
        """Push an item onto the stack."""
        self.items.append(item)

    def pop(self):
        """Pop an item from the stack and return it."""
        if self.is_empty():
            print("Error: Stack is empty")
            return None
        return self.items.pop()

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self.items) == 0

    def peek(self):
        """Peek at the top element of the stack without removing it."""
        return self.items[-1] if not self.is_empty() else None

    def get_stack(self):
        """Get all items in the stack."""
        return self.items

Stack Exercise #1

Determine if brackets are balanced

We’re going to determine whether a set of brackets is balanced by making use of the stack data structure.

A balanced set of brackets is one where the number and type of opening and closing brackets match, and they are properly nested within the string.

Examples of Balanced Brackets:
({[]}), ([]), {[()()]}

Examples of Unbalanced Brackets:
([)], ((, ][, ([]]]

# Simple version: checks only for parentheses
def equation_checker(equation):
    stack = Stack()
    for char in equation:
        if char == "(":
            stack.push(char)
        elif char == ")":
            if stack.pop() is None:
                return False
    return stack.size() == 0

# Example usage:
print(equation_checker("((()))"))  # True
print(equation_checker("(()"))     # False

A more advanced version that can differentiate between all types of brackets and handle all corner cases:

def is_match(p1, p2):
    """Check if p1 and p2 are matching brackets."""
    pairs = { "(": ")", "{": "}", "[": "]" }
    return p1 in pairs and pairs[p1] == p2

def is_paren_balanced(paren_string):
    """
    Check if all types of brackets are balanced in the input string.
    Supports (), {}, [].
    """
    s = Stack()
    for paren in paren_string:
        if paren in "([{":
            s.push(paren)
        elif paren in ")]}":
            if s.is_empty():
                return False
            if not is_match(s.pop(), paren):
                return False
    return s.is_empty()

# Example usage:
print(is_paren_balanced("({[]})"))   # True
print(is_paren_balanced("([)]"))     # False
print(is_paren_balanced("((("))      # False

Stack Exercise #2

Reverse String

There are multiple ways to reverse a string in Python. Here are two approaches:

Pythonic way (using slicing):

input_str = "Test"
print(input_str[::-1])  # Output: tseT

Using a stack:
We push all the characters of the string onto the stack. Due to the Last-In, First-Out (LIFO) property of stacks, popping the characters gives us the string in reverse order.

def reverse_string(input_str):
    stack = Stack()
    result = ""

    # Push all characters onto the stack
    for char in input_str:
        stack.push(char)

    # Pop all characters from the stack and append to result
    while not stack.is_empty():
        result += stack.pop()
    return result

# Example usage:
print(reverse_string("Test"))  # Output: tseT

Stack Exercise #3

Convert decimal integer to binary

Let’s convert a decimal integer to its binary representation using a stack.

The idea:

• Divide the number by 2 repeatedly, pushing the remainder (0 or 1) onto the stack each time.
• Once the number is 0, pop all items from the stack to get the binary string in the correct order.

Why use a stack?
The stack reverses the order of remainders, so the most significant bit ends up at the left.

def convert_int_to_bin(dec_num):
    stack = Stack()
    while dec_num > 0:
        remainder = dec_num % 2
        stack.push(remainder)
        dec_num = dec_num // 2

    bin_num = ""
    while not stack.is_empty():
        bin_num += str(stack.pop())
    return bin_num

# Example usage:
print(convert_int_to_bin(56))  # Output: 111000

# Verification:
print(int(convert_int_to_bin(56), 2) == 56)  # Output: True

Try it: Test with other numbers and see how the stack builds the binary representation!