Check order of parentheses with stack

by

check order of parentheses

Most often we see “Missing Parentheses” error during code execution, this is because compiler checks the order of parentheses during compilation.

This will help student to understand how compiler checks the order of parentheses, and how to use stack to check order.

Working

  • Read string from user.
  • Scan string from left to right.
  • During scanning if we scan open bracket/parentheses e.g. (‘(‘, ‘[‘, ‘{‘), then push it in stack.
  • During scanning if we scan close bracket/parentheses e.g. (‘)’, ‘]’, ‘}’), then pop the top element from the stack and check whether both the element are of same type i.e. if we scan close round bracket ‘)’ then the element which we pop must be an open round bracket ‘(‘ if it is open round bracket ‘(‘ then it is okay. And if it not open round bracket ‘(‘ then it will throw error.
  • If string scan is completed and still there is bracket in stack then it will throw error.
python code to check order of parentheses

class  Stack_to_check_ordered_parantheses  :
    # Creates  an  empty  stack.
    def	__init__(  self  ):
        self.items  =  list()
        self.size=-1
#Author : ITVoyagers Website : itvoyagers.in
    # Returns  True  if  the  stack  is  empty  or  False  otherwise.
    def  isEmpty(  self  ):
        if(self.size==-1):
            return True
        else:
            return False
#Author : ITVoyagers Website : itvoyagers.in
    # Removes  and  returns  the  top  item  on  the  stack.
    def  pop(  self  ):
        if  self.isEmpty():
            print("Stack is empty")
        else:
            #print("the poped elememt is ", self.items.pop())
            return self.items.pop()
            self.size-=1
            
#Author : ITVoyagers Website : itvoyagers.in
    # Push  an  item  onto  the  top  of  the  stack.
    def  push(  self,  item  ):
        self.items.append(item)
        self.size+=1

    #Matching brackets,parantheses,braces
    def matching(self,expression):
        opening='({['
        closing=')}]'
        for b in expression:
            if b in opening:
                self.push(b)
            elif b in closing:
                if self.isEmpty():
                    print("Empty Stack")
                elif closing.index(b)!=opening.index(self.pop()):
                    print("Unordered expression")
                    return False
        print("Ordered expression")
            #Author : ITVoyagers Website : itvoyagers.in
S=Stack_to_check_ordered_parantheses()
sequence=input("Enter a expression to be checkedn")
S.matching(sequence)
#Author : ITVoyagers Website : itvoyagers.in

Output : 

Enter a expression to be checked
{()[]}
Ordered expression

Note : Please note that above program is compatible with Python 3 or higher version.

You can also check following content on conversion, evaluation and other applications of stack

Leave a Comment