The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Exercises with Stacks

Next ►
►

In this section, we will provide practical exercises to reinforce your understanding of stacks. Each exercise will include a problem statement, followed by a solution and an explanation. These exercises will help you apply the concepts and operations related to stacks in real-world scenarios.

Exercise 1: Implement a Stack using an Array

Problem Statement: Implement a stack using an array. Your stack should support the following operations:

  • push(x): Push element x onto the stack.
  • pop(): Remove the element on top of the stack and return it.
  • peek(): Get the top element.
  • isEmpty(): Return whether the stack is empty.

Solution:

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

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
        else:
            return "Stack is empty"

    def peek(self):
        if not self.isEmpty():
            return self.stack[-1]
        else:
            return "Stack is empty"

    def isEmpty(self):
        return len(self.stack) == 0

# Example usage:
s = Stack()
s.push(1)
s.push(2)
print(s.peek())  # Output: 2
print(s.pop())   # Output: 2
print(s.isEmpty())  # Output: False
print(s.pop())   # Output: 1
print(s.isEmpty())  # Output: True

Explanation:

  • The Stack class uses a list (self.stack) to store elements.
  • The push method appends an element to the end of the list.
  • The pop method removes and returns the last element of the list if the stack is not empty.
  • The peek method returns the last element without removing it if the stack is not empty.
  • The isEmpty method checks if the list is empty.

Exercise 2: Reverse a String using a Stack

Problem Statement: Write a function that takes a string as input and uses a stack to reverse the string.

Solution:

def reverseString(s):
    stack = []
    for char in s:
        stack.append(char)
    
    reversed_string = ''
    while stack:
        reversed_string += stack.pop()
    
    return reversed_string

# Example usage:
input_string = "hello"
print(reverseString(input_string))  # Output: "olleh"

Explanation:

  • The function reverseString initializes an empty stack.
  • It iterates over each character in the input string and pushes it onto the stack.
  • It then pops each character from the stack and appends it to the reversed_string.
  • The stack's LIFO (Last In, First Out) property ensures the string is reversed.

Exercise 3: Check for Balanced Parentheses

Problem Statement: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Solution:

def isValid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

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

Explanation:

  • The function isValid uses a stack to keep track of opening brackets.
  • It iterates over each character in the input string.
  • If the character is a closing bracket, it checks if the top element of the stack matches the corresponding opening bracket.
  • If the character is an opening bracket, it pushes it onto the stack.
  • Finally, it returns True if the stack is empty (all brackets are matched), otherwise False.

Common Mistakes and Tips

  1. Not Checking for Empty Stack: When popping from the stack, always check if the stack is empty to avoid errors.
  2. Incorrect Mapping: Ensure the mapping of closing to opening brackets is correct when checking for balanced parentheses.
  3. Edge Cases: Consider edge cases such as an empty string or a string with only one type of bracket.

Conclusion

In this section, we covered practical exercises to help you understand and implement stacks. We implemented a stack using an array, reversed a string using a stack, and checked for balanced parentheses. These exercises should give you a solid foundation in working with stacks and understanding their applications.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved