Count pairs of parentheses sequences such that parentheses are balanced | Python3 program to count the number of pairs of balanced parentheses ; Function to count the number of pairs ; Hashing function to count the opening and closing brackets ; Traverse for all bracket sequences ; Get the string ; Counts the opening and closing required ; Traverse in the string ; If it is a opening bracket ; If openings are there , then close it ; else : Else increase count of closing ; If requirements of openings are there and no closing ; If requirements of closing are there and no opening ; Perfect ; Divide by two since two perfect makes one pair ; Traverse in the open and find corresponding minimum ; Driver Code
import math as mt NEW_LINE def countPairs ( bracks , num ) : NEW_LINE INDENT openn = dict ( ) NEW_LINE close = dict ( ) NEW_LINE cnt = 0 NEW_LINE for i in range ( num ) : NEW_LINE INDENT s = bracks [ i ] NEW_LINE l = len ( s ) NEW_LINE op , cl = 0 , 0 NEW_LINE for j in range ( l ) : NEW_LINE INDENT if ( s [ j ] == ' ( ' ) : NEW_LINE INDENT op += 1 NEW_LINE if ( op ) : NEW_LINE INDENT op -= 1 NEW_LINE cl += 1 NEW_LINE DEDENT DEDENT DEDENT if ( op and cl == 0 ) : NEW_LINE INDENT if op in openn . keys ( ) : NEW_LINE INDENT openn [ op ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT openn [ op ] = 1 NEW_LINE DEDENT DEDENT if ( cl and op == 0 ) : NEW_LINE INDENT if cl in openn . keys ( ) : NEW_LINE INDENT close [ cl ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT close [ cl ] = 1 NEW_LINE DEDENT DEDENT if ( op == 0 and cl == 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT cnt = cnt // 2 NEW_LINE for it in openn : NEW_LINE INDENT cnt += min ( openn [ it ] , close [ it ] ) NEW_LINE DEDENT return cnt NEW_LINE DEDENT bracks = [ " ) ( ) ) " , " ) " , " ( ( " , " ( ( " , " ( " , " ) " , " ) " ] NEW_LINE num = len ( bracks ) NEW_LINE print ( countPairs ( bracks , num ) ) NEW_LINE