Check if a Regular Bracket Sequence can be formed with concatenation of given strings | C ++ program for the above approach ; Function to check possible RBS from the given strings ; Stores the values { sum , min_prefix } ; Iterate over the range ; Stores the total sum ; Stores the minimum prefix ; Check for minimum prefix ; Store these values in vector ; Make two pair vectors pos and neg ; Store values according to the mentioned approach ; Sort the positive vector ; Stores the extra count of open brackets ; No valid bracket sequence can be formed ; Sort the negative vector ; Stores the count of the negative elements ; No valid bracket sequence can be formed ; Check if open is equal to negative ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int checkRBS ( vector < string > S ) { int N = S . size ( ) ; vector < pair < int , int > > v ( N ) ; for ( int i = 0 ; i < N ; ++ i ) { string s = S [ i ] ; int sum = 0 ; int pre = 0 ; for ( char c : s ) { if ( c == ' ( ' ) { ++ sum ; } else { -- sum ; } pre = min ( sum , pre ) ; } v [ i ] = { sum , pre } ; } vector < pair < int , int > > pos ; vector < pair < int , int > > neg ; for ( int i = 0 ; i < N ; ++ i ) { if ( v [ i ] . first >= 0 ) { pos . push_back ( { - v [ i ] . second , v [ i ] . first } ) ; } else { neg . push_back ( { v [ i ] . first - v [ i ] . second , - v [ i ] . first } ) ; } } sort ( pos . begin ( ) , pos . end ( ) ) ; int open = 0 ; for ( auto p : pos ) { if ( open - p . first >= 0 ) { open += p . second ; } else { cout << " No " << " STRNEWLINE " ; return 0 ; } } sort ( neg . begin ( ) , neg . end ( ) ) ; int negative = 0 ; for ( auto p : neg ) { if ( negative - p . first >= 0 ) { negative += p . second ; } else { cout << " No STRNEWLINE " ; return 0 ; } } if ( open != negative ) { cout << " No STRNEWLINE " ; return 0 ; } cout << " Yes STRNEWLINE " ; return 0 ; } int main ( ) { vector < string > arr = { " ) " , " ( ) ( " } ; checkRBS ( arr ) ; return 0 ; }