Number of balanced bracket expressions that can be formed from a string | 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 ; Driver Code
MAX = 300 NEW_LINE def checkFunc ( i , j , st ) : NEW_LINE INDENT if ( st [ i ] == ' ( ' and st [ j ] == ' ) ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( st [ i ] == ' ( ' and st [ j ] == ' ? ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( st [ i ] == ' ? ' and st [ j ] == ' ) ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( st [ i ] == ' [ ' and st [ j ] == ' ] ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( st [ i ] == ' [ ' and st [ j ] == ' ? ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( st [ i ] == ' ? ' and st [ j ] == ' ] ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( st [ i ] == ' { ' and st [ j ] == ' } ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( st [ i ] == ' { ' and st [ j ] == ' ? ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( st [ i ] == ' ? ' and st [ j ] == ' } ' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT def countRec ( start , end , dp , st ) : NEW_LINE INDENT sum = 0 NEW_LINE if ( start > end ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ start ] [ end ] != - 1 ) : NEW_LINE INDENT return dp [ start ] [ end ] NEW_LINE DEDENT r = 0 NEW_LINE for i in range ( start + 1 , end + 1 , 2 ) : NEW_LINE INDENT if ( checkFunc ( start , i , st ) ) : NEW_LINE INDENT sum = ( sum + countRec ( start + 1 , i - 1 , dp , st ) * countRec ( i + 1 , end , dp , st ) ) NEW_LINE DEDENT elif ( st [ start ] == ' ? ' and st [ i ] == ' ? ' ) : NEW_LINE INDENT sum = ( sum + countRec ( start + 1 , i - 1 , dp , st ) * countRec ( i + 1 , end , dp , st ) * 3 ) NEW_LINE DEDENT DEDENT dp [ start ] [ end ] = sum NEW_LINE return dp [ start ] [ end ] NEW_LINE DEDENT def countWays ( st ) : NEW_LINE INDENT n = len ( st ) NEW_LINE if ( n % 2 == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT dp = [ [ - 1 for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE return countRec ( 0 , n - 1 , dp , st ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " ( ? ( [ ? ) ] ? } ? " NEW_LINE print ( countWays ( st ) ) NEW_LINE DEDENT