Number of balanced bracket expressions that can be formed from a string | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long int lli ; const int MAX = 300 ; int checkFunc ( int i , int j , string st ) { if ( st [ i ] == ' ( ' && st [ j ] == ' ) ' ) return 1 ; if ( st [ i ] == ' ( ' && st [ j ] == ' ? ' ) return 1 ; if ( st [ i ] == ' ? ' && st [ j ] == ' ) ' ) return 1 ; if ( st [ i ] == ' [ ' && st [ j ] == ' ] ' ) return 1 ; if ( st [ i ] == ' [ ' && st [ j ] == ' ? ' ) return 1 ; if ( st [ i ] == ' ? ' && st [ j ] == ' ] ' ) return 1 ; if ( st [ i ] == ' { ' && st [ j ] == ' } ' ) return 1 ; if ( st [ i ] == ' { ' && st [ j ] == ' ? ' ) return 1 ; if ( st [ i ] == ' ? ' && st [ j ] == ' } ' ) return 1 ; return 0 ; } int countRec ( int start , int end , int dp [ ] [ MAX ] , string st ) { int sum = 0 ; if ( start > end ) return 1 ; if ( dp [ start ] [ end ] != -1 ) return dp [ start ] [ end ] ; lli i , r = 0 ; for ( i = start + 1 ; i <= end ; i += 2 ) { if ( checkFunc ( start , i , st ) ) { sum = sum + countRec ( start + 1 , i - 1 , dp , st ) * countRec ( i + 1 , end , dp , st ) ; } else if ( st [ start ] == ' ? ' && st [ i ] == ' ? ' ) { sum = sum + countRec ( start + 1 , i - 1 , dp , st ) * countRec ( i + 1 , end , dp , st ) * 3 ; } } return dp [ start ] [ end ] = sum ; } int countWays ( string st ) { int n = st . length ( ) ; if ( n % 2 == 1 ) return 0 ; int dp [ MAX ] [ MAX ] ; memset ( dp , -1 , sizeof ( dp ) ) ; return countRec ( 0 , n - 1 , dp , st ) ; } int main ( ) { string st = " ( ? ( [ ? ) ] ? } ? " ; cout << countWays ( st ) ; return 0 ; }