Balanced parentheses in Python

In this tutorial, we will learn how to find out whether the given expression has balanced parentheses or not using Python. The appropriate data structure to solve this problem is Stack. This is one of the important tasks of a compiler. The compiler uses this method to find the missing parentheses in the code.

Balanced parentheses in an Expression

stack
In the above example we have taken string ‘{[({})[]]}‘ as input and converted it to list. And also created an object ‘Stk’ of class ‘Stack’. Now we will traverse the list ‘lst’.

def check(obj,lst):
    d={'(':')','{':'}','[':']'}
    for item in lst:
        if( item == '(' or item == '{' or item == '[' ):
            Stk.push(item)
        elif( item == ')' or item == '}' or item == ']' ):
            value = Stk.pop()
            if d[value] != item :
                return 'Not Balanced'
        else:
             continue
    if Stk.empty():
        return 'Balanced'
    else:
        return 'Not Balanced'
  • If the element is a starting bracket( ‘{‘, ‘[‘, ‘(‘ ), append it to the Stack.
  • Similarly for closing bracket( ‘}’, ‘]’, ‘)’ ), pop an element from he Stack.
  • Compare the poped element with the closing bracket. While the popped element is not the matching starting bracket, we can conclude that the parentheses are not balanced.
  • If the elements are not a starting or closing bracket, we can assume that they are other characters of the expression. As a result, we can skip that iteration using the continue statement.
  • Finally, if the Stack is empty after the traversal, the parentheses are said to be balanced else it is not balanced.

Example:

Input: {(a+b)*(b+c)+(x/z)}
Output: 'Balanced'

Input: {[({})[]}
Output: 'Not Balanced'

Here is how the complete Python code should look like:

class Stack:
    def __init__(obj):
        obj.element = []
    def empty(obj) :
        return obj.element == []
    def push(obj, item):
        obj.element.append(item)
    def pop(obj):
        return obj.element.pop()
    def check(obj,lst):
        d={'(':')','{':'}','[':']'}
        for item in lst:
            if( item == '(' or item == '{' or item == '[' ):
                Stk.push(item)
            elif( item == ')' or item == '}' or item == ']' ):
                value = Stk.pop()
                if d[value] != item :
                    return 'Not Balanced'
            else:
                continue
        if Stk.empty():
            return 'Balanced'
        else:
            return 'Not Balanced'

Stk = Stack()
lst = list(input())
print(Stk.check(lst))

Know more about Python Stack and OOPS concepts.

Thank you..!

Leave a Reply

Your email address will not be published. Required fields are marked *