Count pairs of parentheses sequences such that parentheses are balanced | C ++ 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 ; else Closing 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countPairs ( string bracks [ ] , int num ) { unordered_map < int , int > open , close ; int cnt = 0 ; for ( int i = 0 ; i < num ; i ++ ) { string s = bracks [ i ] ; int l = s . length ( ) ; int op = 0 , cl = 0 ; for ( int j = 0 ; j < l ; j ++ ) { if ( s [ j ] == ' ( ' ) op ++ ; { if ( op ) op -- ; cl ++ ; } } if ( op && ! cl ) open [ op ] ++ ; if ( cl && ! op ) close [ cl ] ++ ; if ( ! op && ! cl ) cnt ++ ; } cnt = cnt / 2 ; for ( auto it : open ) cnt += min ( it . second , close [ it . first ] ) ; return cnt ; } int main ( ) { string bracks [ ] = { " ) ( ) ) " , " ) " , " ( ( " , " ( ( " , " ( " , " ) " , " ) " } ; int num = sizeof ( bracks ) / sizeof ( bracks [ 0 ] ) ; cout << countPairs ( bracks , num ) ; }