Boolean Parenthesization Problem | DP | CountWays function ; Base Condition ; Count number of True in left Partition ; Count number of False in left Partition ; Count number of True in right Partition ; Count number of False in right Partition ; Evaluate AND operation ; Evaluate OR operation ; Evaluate XOR operation ; Driver code ; We obtain the string T | T & F ^ T ; There are 4 ways ( ( T T ) & ( F ^ T ) ) , ( T | ( T & ( F ^ T ) ) ) , ( ( ( T T ) & F ) ^ T ) and ( T | ( ( T & F ) ^ T ) )
def countWays ( N , S ) : NEW_LINE INDENT dp = [ [ [ - 1 for k in range ( 2 ) ] for i in range ( N + 1 ) ] for j in range ( N + 1 ) ] NEW_LINE return parenthesis_count ( S , 0 , N - 1 , 1 , dp ) NEW_LINE DEDENT def parenthesis_count ( Str , i , j , isTrue , dp ) : NEW_LINE INDENT if ( i > j ) : NEW_LINE return 0 NEW_LINE if ( i == j ) : NEW_LINE if ( isTrue == 1 ) : NEW_LINE INDENT return 1 if Str [ i ] == ' T ' else 0 NEW_LINE DEDENT else : NEW_LINE INDENT return 1 if Str [ i ] == ' F ' else 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] [ isTrue ] != - 1 ) : NEW_LINE return dp [ i ] [ j ] [ isTrue ] NEW_LINE temp_ans = 0 NEW_LINE for k in range ( i + 1 , j , 2 ) : NEW_LINE if ( dp [ i ] [ k - 1 ] [ 1 ] != - 1 ) : NEW_LINE INDENT leftTrue = dp [ i ] [ k - 1 ] [ 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT leftTrue = parenthesis_count ( Str , i , k - 1 , 1 , dp ) NEW_LINE DEDENT if ( dp [ i ] [ k - 1 ] [ 0 ] != - 1 ) : NEW_LINE INDENT leftFalse = dp [ i ] [ k - 1 ] [ 0 ] NEW_LINE DEDENT else : NEW_LINE INDENT leftFalse = parenthesis_count ( Str , i , k - 1 , 0 , dp ) NEW_LINE DEDENT if ( dp [ k + 1 ] [ j ] [ 1 ] != - 1 ) : NEW_LINE INDENT rightTrue = dp [ k + 1 ] [ j ] [ 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT rightTrue = parenthesis_count ( Str , k + 1 , j , 1 , dp ) NEW_LINE DEDENT if ( dp [ k + 1 ] [ j ] [ 0 ] != - 1 ) : NEW_LINE INDENT rightFalse = dp [ k + 1 ] [ j ] [ 0 ] NEW_LINE DEDENT else : NEW_LINE INDENT rightFalse = parenthesis_count ( Str , k + 1 , j , 0 , dp ) NEW_LINE DEDENT if ( Str [ k ] == ' & ' ) : NEW_LINE INDENT if ( isTrue == 1 ) : NEW_LINE temp_ans = temp_ans + leftTrue * rightTrue NEW_LINE else : NEW_LINE temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse NEW_LINE DEDENT elif ( Str [ k ] == ' ▁ ' ) : NEW_LINE INDENT if ( isTrue == 1 ) : NEW_LINE temp_ans = temp_ans + leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue NEW_LINE else : NEW_LINE temp_ans = temp_ans + leftFalse * rightFalse NEW_LINE DEDENT elif ( Str [ k ] == ' ^ ' ) : NEW_LINE INDENT if ( isTrue == 1 ) : NEW_LINE temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue NEW_LINE else : NEW_LINE temp_ans = temp_ans + leftTrue * rightTrue + leftFalse * rightFalse NEW_LINE DEDENT dp [ i ] [ j ] [ isTrue ] = temp_ans NEW_LINE return temp_ans NEW_LINE DEDENT symbols = " TTFT " NEW_LINE operators = " | & ^ " NEW_LINE S = " " NEW_LINE j = 0 NEW_LINE for i in range ( len ( symbols ) ) : NEW_LINE INDENT S = S + symbols [ i ] NEW_LINE if ( j < len ( operators ) ) : NEW_LINE INDENT S = S + operators [ j ] NEW_LINE j += 1 NEW_LINE DEDENT DEDENT N = len ( S ) NEW_LINE print ( countWays ( N , S ) ) NEW_LINE