Boolean Parenthesization Problem | DP | Returns count of all possible parenthesizations that lead to result true for a boolean expression with symbols like true and false and operators like & , | and ^ filled between symbols ; Fill diaginal entries first All diagonal entries in T [ i ] [ i ] are 1 if symbol [ i ] is T ( true ) . Similarly , all F [ i ] [ i ] entries are 1 if symbol [ i ] is F ( False ) ; Now fill T [ i ] [ i + 1 ] , T [ i ] [ i + 2 ] , T [ i ] [ i + 3 ] ... in order And F [ i ] [ i + 1 ] , F [ i ] [ i + 2 ] , F [ i ] [ i + 3 ] ... in order ; Find place of parenthesization using current value of gap ; Store Total [ i ] [ k ] and Total [ k + 1 ] [ j ] ; Follow the recursive formulas according to the current operator ; Driver Code ; There are 4 ways ( ( T T ) & ( F ^ T ) ) , ( T | ( T & ( F ^ T ) ) ) , ( ( ( T T ) & F ) ^ T ) and ( T | ( ( T & F ) ^ T ) )
def countParenth ( symb , oper , n ) : NEW_LINE INDENT F = [ [ 0 for i in range ( n + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE T = [ [ 0 for i in range ( n + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if symb [ i ] == ' F ' : NEW_LINE INDENT F [ i ] [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT F [ i ] [ i ] = 0 NEW_LINE DEDENT if symb [ i ] == ' T ' : NEW_LINE INDENT T [ i ] [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT T [ i ] [ i ] = 0 NEW_LINE DEDENT DEDENT for gap in range ( 1 , n ) : NEW_LINE INDENT i = 0 NEW_LINE for j in range ( gap , n ) : NEW_LINE INDENT T [ i ] [ j ] = F [ i ] [ j ] = 0 NEW_LINE for g in range ( gap ) : NEW_LINE INDENT k = i + g NEW_LINE tik = T [ i ] [ k ] + F [ i ] [ k ] NEW_LINE tkj = T [ k + 1 ] [ j ] + F [ k + 1 ] [ j ] NEW_LINE if oper [ k ] == ' & ' : NEW_LINE INDENT T [ i ] [ j ] += T [ i ] [ k ] * T [ k + 1 ] [ j ] NEW_LINE F [ i ] [ j ] += ( tik * tkj - T [ i ] [ k ] * T [ k + 1 ] [ j ] ) NEW_LINE DEDENT if oper [ k ] == ' | ' : NEW_LINE INDENT F [ i ] [ j ] += F [ i ] [ k ] * F [ k + 1 ] [ j ] NEW_LINE T [ i ] [ j ] += ( tik * tkj - F [ i ] [ k ] * F [ k + 1 ] [ j ] ) NEW_LINE DEDENT if oper [ k ] == ' ^ ' : NEW_LINE INDENT T [ i ] [ j ] += ( F [ i ] [ k ] * T [ k + 1 ] [ j ] + T [ i ] [ k ] * F [ k + 1 ] [ j ] ) NEW_LINE F [ i ] [ j ] += ( T [ i ] [ k ] * T [ k + 1 ] [ j ] + F [ i ] [ k ] * F [ k + 1 ] [ j ] ) NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT return T [ 0 ] [ n - 1 ] NEW_LINE DEDENT symbols = " TTFT " NEW_LINE operators = " | & ^ " NEW_LINE n = len ( symbols ) NEW_LINE print ( countParenth ( symbols , operators , n ) ) NEW_LINE