Stacks

Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.
Here is the lecture on stacks by Prof Naveen Garg.

A very simple implementation of a Stack in Python is explained below.


#class for defining a stack
class Stack:
    def __init__(self):
        self.items = []
        
    #method for pushing an item on a stack
    def push(self,item):
        self.items.append(item)
        
    #method for popping an item from a stack
    def pop(self):
        return self.items.pop()
    
    #method to check whether the stack is empty or not
    def isEmpty(self):
        return (self.items == [])
    
    #method to get the top of the stack
    def topOfStack(self):
        return len(self.items)
    
    def __str__(self):
        return str(self.items)
    

if __name__ == "__main__":
    stck = Stack()

    stck.push(5)
    stck.push(10)
    stck.push(15)
    stck.push(20)

    print stck
    #Output = [5, 10, 15, 20]

    stck.pop()

    print stck
    #Output = [5, 10, 15]

    print stck.topOfStack()
    #Output = 3

We will learn about how to implement stacks using Linked Lists later, when we cover Linked Lists. At this moment we will use the stack created above for solving most of the problems related to Stacks.

1. Write a code for showing how stacks can be used for checking balancing of symbols.

Sample Input: “([)]”
Sample Output: False

Sample Input : “{{([][])}()}”
Sample Output : True

Soln: The algorithm is as follows:
Step 1. Create a stack.
Step 2. Scan the input and while the end is not reached perform the following steps:
Step 2a. If the character read is not a symbol to be balanced then ignore it.
Step 2b. If the character is an opening symbol like “(,{ or [” then push it onto the stack.
Step 2c. If the character is a closing symbol like “), } or ]” then if the stack is empty then return that the given input is unbalanced, else pop the symbol from the top of the stack.
Step 2d. If the symbol popped is not the corresponding opening symbol of the closing symbol currently being scanned then return that the given input is unbalanced.

The Python program implementing the problem is as follows:

class Stack:
    def __init__(self):
        self.items = []
        
    #method for pushing an item on a stack
    def push(self,item):
        self.items.append(item)
        
    #method for popping an item from a stack
    def pop(self):
        return self.items.pop()
    
    #method to check whether the stack is empty or not
    def isEmpty(self):
        return (self.items == [])
    
    #method to get the top of the stack
    def topOfStack(self):
        return len(self.items)
    
    def __str__(self):
        return str(self.items)
    
def matches(top,symbol):
    openingSymbols = "({["
    closingSymbols = ")}]"
    
    return openingSymbols.index(top) == closingSymbols.index(symbol)


def checkBalance(input):
    symbolstack = Stack()
    balanced = False
    for symbols in input:
        if symbols in ["(","{","["]:
            symbolstack.push(symbols)
        else:
            if symbolstack.isEmpty():
                balanced = False
            else:
                topSymbol = symbolstack.pop()
                if not matches(topSymbol,symbols):
                    balanced = False
                else:
                    balanced = True
                    
    return balanced

print checkBalance("([)]") 
'''Output: False'''

print checkBalance("{{([][])}()}") 
'''Output: True''' 

2. Convert a decimal number into the number of a particular given base.

Sample Input: decimal = 25 base = 2
Sample Output: 11001
Soln:

class Stack:
    def __init__(self):
        self.items = []
        
    #method for pushing an item on a stack
    def push(self,item):
        self.items.append(item)
        
    #method for popping an item from a stack
    def pop(self):
        return self.items.pop()
    
    #method to check whether the stack is empty or not
    def isEmpty(self):
        return (self.items == [])
    
    #method to get the top of the stack
    def topOfStack(self):
        return len(self.items)
    
    def __str__(self):
        return str(self.items)


def baseConversion(decimalNum,base):
    digits = "0123456789ABCDEF"
    
    remainderStack = Stack()
    
    while (decimalNum > 0):
        remainderStack.push(decimalNum % base)
        decimalNum //= base
    
    convertedString = ""    
    while not remainderStack.isEmpty():
        convertedString = convertedString + digits[remainderStack.pop()]
        
    return convertedString

print baseConversion(25,2)
'''Output 11001'''

print baseConversion(1000,16)
'''Output 3E8'''

3. Check whether a given string is a palindrome or not?

Sample Input: “madam”

Sample Output: True

Soln:

class Stack:
    def __init__(self):
        self.items = []
        
    #method for pushing an item on a stack
    def push(self,item):
        self.items.append(item)
        
    #method for popping an item from a stack
    def pop(self):
        return self.items.pop()
    
    #method to check whether the stack is empty or not
    def isEmpty(self):
        return (self.items == [])
    
    #method to get the top of the stack
    def topOfStack(self):
        return len(self.items)
    
    def __str__(self):
        return str(self.items)


def isPalindrome(str):
    strStack = Stack()
    palindrome = False
    
    for char in str:
        strStack.push(char)
        
    for char in str:
        if char == strStack.pop():
            palindrome = True
        else:
            palindrome = False
            
    return palindrome

print isPalindrome("madam")

Advertisements

Stacks

The concept behind stacks can be learnt from the following video tutorial

A program that implements Stacks is as follows:


#class for defining a stack
class Stack:
    def __init__(self):
        self.items = []
        
    #method for pushing an item on a stack
    def push(self,item):
        self.items.append(item)
        
    #method for popping an item from a stack
    def pop(self):
        return self.items.pop()
    
    #method to check whether the stack is empty or not
    def isEmpty(self):
        return (self.items == [])
    
    #method to get the top of the stack
    def topOfStack(self):
        return len(self.items)
    
    def __str__(self):
        return str(self.items)
    


stck = Stack()

stck.push(5)
stck.push(10)
stck.push(15)
stck.push(20)

print stck
#Output = [5, 10, 15, 20]

stck.pop()

print stck
#Output = [5, 10, 15]

print stck.topOfStack()
#Output = 3