Check if a Regular Bracket Sequence can be formed with concatenation of given strings | 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 ; 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
def checkRBS ( S ) : NEW_LINE INDENT N = len ( S ) NEW_LINE v = [ 0 ] * ( N ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT s = S [ i ] NEW_LINE sum = 0 NEW_LINE pre = 0 NEW_LINE for c in s : NEW_LINE INDENT if ( c == ' ( ' ) : NEW_LINE INDENT sum += 1 NEW_LINE DEDENT else : NEW_LINE INDENT sum -= 1 NEW_LINE DEDENT pre = min ( sum , pre ) NEW_LINE DEDENT v [ i ] = [ sum , pre ] NEW_LINE DEDENT pos = [ ] NEW_LINE neg = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( v [ i ] [ 0 ] >= 0 ) : NEW_LINE INDENT pos . append ( [ - v [ i ] [ 1 ] , v [ i ] [ 0 ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT neg . append ( [ v [ i ] [ 0 ] - v [ i ] [ 1 ] , - v [ i ] [ 0 ] ] ) NEW_LINE DEDENT DEDENT pos . sort ( ) NEW_LINE open = 0 NEW_LINE for p in pos : NEW_LINE INDENT if ( open - p [ 0 ] >= 0 ) : NEW_LINE INDENT open += p [ 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE return 0 NEW_LINE DEDENT DEDENT neg . sort ( ) NEW_LINE negative = 0 NEW_LINE for p in neg : NEW_LINE INDENT if ( negative - p [ 0 ] >= 0 ) : NEW_LINE INDENT negative += p [ 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE return 0 NEW_LINE DEDENT DEDENT if ( open != negative ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return 0 NEW_LINE DEDENT print ( " Yes " ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : arr = [ " ) " , " ( ) ( " ] NEW_LINE INDENT checkRBS ( arr ) NEW_LINE DEDENT