Data Structure in Python:Stack — Determine If Parenthesis Are Balanced

So let’s move to the next part of learning Data Structure in python are we are on stack.

This is the second blog from that series and we are using the stack class from the First blog see here:

Data Structure in Python: Convert Integer to Binary using Stack

If you want you can check it out as it contain the stack class which we are using for now:

# create a class Stack

class Stack():
    def __init__(self):
        self.items  = []
    
    def push(self,item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()
    
    def is_empty(self):
        return self.items == []

    def get_top(self):
        if not self.is_empty():
            return self.items[-1]


    def get_stack(self):
        return self.items

Now just save this class in same folder as this parenthesis problem file

Problem :Using stack to check whether or not a string has a balanced usage of parenthesis.

example:

(),{()[]},{([])} ==> Balanced Parenthesis

()),{{{},[][]( ==> Non-Balanced Parenthesis

The basic idea is that in set of parenthesis we push all the opening parenthesis and check when a closing parenthesis occur and we pop that out and check with the top element of the stack and that further go on.

lets take an example : ([])

loop through the all set of character as ‘(‘ , and ‘[‘ is opening parenthesis we simply push through the stack after ‘]’ is encountered we pop the top element and check whether the popped parenthesis is equal to the closing parenthesis or not and it further goes on and if the stack is empty at end then we declare Balanced Parenthesis.

Now let’s understand for the Non-Balanced example:(()

In this loop starts and two opening Parenthesis ‘(‘ pushed to stack after that when ‘)’ Parenthesis is encountered we popped the top element and compare the closing Parenthesis with it and if equal to move forward to loop and now loop ended but our stack is not empty that means it is Non-Balanced .

Now let’s code to check whether we understand it or not:

We are using the Stack from file stack.py so we have to import it just make sure stack.py and Is_Balanced_Paranthesis.py file

from stack import Stack
# taking top in p and current parenthesis in q
def is_match(p,q):
    if p =='(' and q == ')':
        return True
    elif p =='{' and q == '}':
        return True
    elif p =='[' and q == ']':
        return True
    else:
        return False
def is_paren_balanced(paren_string):
    s = Stack()
    is_balanced = True
    index  = 0
 
    while index < len(paren_string) and is_balanced:
        paren = paren_string[index]
        if paren in '({[':
            s.push(paren)   # we are using push from Stack Class and
                            # s is the object of Stack class
        else:
            if s.is_empty():
                is_balanced = False
            else:
                top = s.pop() #if closing found then pop the top 
                if not is_match(top,paren):
                    is_balanced = False
       index = index + 1
    
    if s.is_empty and is_balanced:
        return True 
    else:
        return False
#check 
print(is_paren_balanced('()()'))
print(is_paren_balanced('{{{]'))

the output will we :

True
False