Check for balanced parentheses in an expression | O ( 1 ) space | Function1 to match closing bracket ; Function1 to match opening bracket ; Function to check balanced parentheses ; helper variables ; Handling case of opening parentheses ; Handling case of closing parentheses ; If corresponding matching opening parentheses doesn 't lie in given  interval return 0 ; else continue ; If corresponding closing parentheses doesn 't lie in given interval, return 0 ; if found , now check for each opening and closing parentheses in this interval ; Driver Code
def matchClosing ( X , start , end , open , close ) : NEW_LINE INDENT c = 1 NEW_LINE i = start + 1 NEW_LINE while ( i <= end ) : NEW_LINE INDENT if ( X [ i ] == open ) : NEW_LINE INDENT c += 1 NEW_LINE DEDENT elif ( X [ i ] == close ) : NEW_LINE INDENT c -= 1 NEW_LINE DEDENT if ( c == 0 ) : NEW_LINE INDENT return i NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return i NEW_LINE DEDENT def matchingOpening ( X , start , end , open , close ) : NEW_LINE INDENT c = - 1 NEW_LINE i = end - 1 NEW_LINE while ( i >= start ) : NEW_LINE INDENT if ( X [ i ] == open ) : NEW_LINE INDENT c += 1 NEW_LINE DEDENT elif ( X [ i ] == close ) : NEW_LINE INDENT c -= 1 NEW_LINE DEDENT if ( c == 0 ) : NEW_LINE INDENT return i NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT return - 1 NEW_LINE DEDENT def isBalanced ( X , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT if ( X [ i ] == ' ( ' ) : NEW_LINE INDENT j = matchClosing ( X , i , n - 1 , ' ( ' , ' ) ' ) NEW_LINE DEDENT elif ( X [ i ] == ' { ' ) : NEW_LINE INDENT j = matchClosing ( X , i , n - 1 , ' { ' , ' } ' ) NEW_LINE DEDENT elif ( X [ i ] == ' [ ' ) : NEW_LINE INDENT j = matchClosing ( X , i , n - 1 , ' [ ' , ' ] ' ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( X [ i ] == ' ) ' ) : NEW_LINE INDENT j = matchingOpening ( X , 0 , i , ' ( ' , ' ) ' ) NEW_LINE DEDENT elif ( X [ i ] == ' } ' ) : NEW_LINE INDENT j = matchingOpening ( X , 0 , i , ' { ' , ' } ' ) NEW_LINE DEDENT elif ( X [ i ] == ' ] ' ) : NEW_LINE INDENT j = matchingOpening ( X , 0 , i , ' [ ' , ' ] ' ) NEW_LINE DEDENT if ( j < 0 or j >= i ) : NEW_LINE INDENT return False NEW_LINE DEDENT continue NEW_LINE DEDENT if ( j >= n or j < 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT start = i NEW_LINE end = j NEW_LINE for k in range ( start + 1 , end ) : NEW_LINE INDENT if ( X [ k ] == ' ( ' ) : NEW_LINE INDENT x = matchClosing ( X , k , end , ' ( ' , ' ) ' ) NEW_LINE if ( not ( k < x and x < end ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT elif ( X [ k ] == ' ) ' ) : NEW_LINE INDENT x = matchingOpening ( X , start , k , ' ( ' , ' ) ' ) NEW_LINE if ( not ( start < x and x < k ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if ( X [ k ] == ' { ' ) : NEW_LINE INDENT x = matchClosing ( X , k , end , ' { ' , ' } ' ) NEW_LINE if ( not ( k < x and x < end ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT elif ( X [ k ] == ' } ' ) : NEW_LINE INDENT x = matchingOpening ( X , start , k , ' { ' , ' } ' ) NEW_LINE if ( not ( start < x and x < k ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if ( X [ k ] == ' [ ' ) : NEW_LINE INDENT x = matchClosing ( X , k , end , ' [ ' , ' ] ' ) NEW_LINE if ( not ( k < x and x < end ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT elif ( X [ k ] == ' ] ' ) : NEW_LINE INDENT x = matchingOpening ( X , start , k , ' [ ' , ' ] ' ) NEW_LINE if ( not ( start < x and x < k ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT DEDENT DEDENT return True NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT X = " [ ( ) ] ( ) " NEW_LINE n = 6 NEW_LINE if ( isBalanced ( X , n ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT Y = " [ [ ( ) ] ] ) " NEW_LINE n = 7 NEW_LINE if ( isBalanced ( Y , n ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT