Number of balanced bracket expressions that can be formed from a string | Java program to find number of balanced bracket expressions possible ; Max string length ; Function to check whether index start and end can form a bracket pair or not ; Check for brackets ( ) ; Check for brackets [ ] ; Check for brackets { } ; Function to find number of proper bracket expressions ; If starting index is greater than ending index ; If dp [ start ] [ end ] has already been computed ; Search for the bracket in from next index ; If bracket pair is formed , add number of combination ; If ? comes then all three bracket expressions are possible ; Return answer ; If n is odd , string cannot be balanced ; Driving function
class GFG { static int MAX = 300 ; static int checkFunc ( int i , int j , String st ) { if ( st . charAt ( i ) == ' ( ' && st . charAt ( j ) == ' ) ' ) return 1 ; if ( st . charAt ( i ) == ' ( ' && st . charAt ( j ) == ' ? ' ) return 1 ; if ( st . charAt ( i ) == ' ? ' && st . charAt ( j ) == ' ) ' ) return 1 ; if ( st . charAt ( i ) == ' [ ' && st . charAt ( j ) == ' ] ' ) return 1 ; if ( st . charAt ( i ) == ' [ ' && st . charAt ( j ) == ' ? ' ) return 1 ; if ( st . charAt ( i ) == ' ? ' && st . charAt ( j ) == ' ] ' ) return 1 ; if ( st . charAt ( i ) == ' { ' && st . charAt ( j ) == ' } ' ) return 1 ; if ( st . charAt ( i ) == ' { ' && st . charAt ( j ) == ' ? ' ) return 1 ; if ( st . charAt ( i ) == ' ? ' && st . charAt ( j ) == ' } ' ) return 1 ; return 0 ; } static int countRec ( int start , int end , int dp [ ] [ ] , String st ) { int sum = 0 ; if ( start > end ) return 1 ; if ( dp [ start ] [ end ] != - 1 ) return dp [ start ] [ end ] ; int i , r = 0 ; for ( i = start + 1 ; i <= end ; i += 2 ) { if ( checkFunc ( start , i , st ) == 1 ) { sum = sum + countRec ( start + 1 , i - 1 , dp , st ) * countRec ( i + 1 , end , dp , st ) ; } else if ( st . charAt ( start ) == ' ? ' && st . charAt ( i ) == ' ? ' ) { sum = sum + countRec ( start + 1 , i - 1 , dp , st ) * countRec ( i + 1 , end , dp , st ) * 3 ; } } return dp [ start ] [ end ] = sum ; } static int countWays ( String st ) { int n = st . length ( ) ; if ( n % 2 == 1 ) return 0 ; int dp [ ] [ ] = new int [ MAX ] [ MAX ] ; for ( int i = 0 ; i < MAX ; i ++ ) for ( int j = 0 ; j < MAX ; j ++ ) dp [ i ] [ j ] = - 1 ; return countRec ( 0 , n - 1 , dp , st ) ; } public static void main ( String [ ] args ) { String st = " ( ? ( [ ? ) ] ? } ? " ; System . out . println ( countWays ( st ) ) ; } }