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 ) )
#include <cstring> NEW_LINE #include <iostream> NEW_LINE using namespace std ; int countParenth ( char symb [ ] , char oper [ ] , int n ) { int F [ n ] [ n ] , T [ n ] [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { F [ i ] [ i ] = ( symb [ i ] == ' F ' ) ? 1 : 0 ; T [ i ] [ i ] = ( symb [ i ] == ' T ' ) ? 1 : 0 ; } for ( int gap = 1 ; gap < n ; ++ gap ) { for ( int i = 0 , j = gap ; j < n ; ++ i , ++ j ) { T [ i ] [ j ] = F [ i ] [ j ] = 0 ; for ( int g = 0 ; g < gap ; g ++ ) { int k = i + g ; int tik = T [ i ] [ k ] + F [ i ] [ k ] ; int tkj = T [ k + 1 ] [ j ] + F [ k + 1 ] [ j ] ; if ( oper [ k ] == ' & ' ) { T [ i ] [ j ] += T [ i ] [ k ] * T [ k + 1 ] [ j ] ; F [ i ] [ j ] += ( tik * tkj - T [ i ] [ k ] * T [ k + 1 ] [ j ] ) ; } if ( oper [ k ] == ' ▁ ' ) { F [ i ] [ j ] += F [ i ] [ k ] * F [ k + 1 ] [ j ] ; T [ i ] [ j ] += ( tik * tkj - F [ i ] [ k ] * F [ k + 1 ] [ j ] ) ; } if ( oper [ k ] == ' ^ ' ) { T [ i ] [ j ] += F [ i ] [ k ] * T [ k + 1 ] [ j ] + T [ i ] [ k ] * F [ k + 1 ] [ j ] ; F [ i ] [ j ] += T [ i ] [ k ] * T [ k + 1 ] [ j ] + F [ i ] [ k ] * F [ k + 1 ] [ j ] ; } } } } return T [ 0 ] [ n - 1 ] ; } int main ( ) { char symbols [ ] = " TTFT " ; char operators [ ] = " | & ^ " ; int n = strlen ( symbols ) ; cout << countParenth ( symbols , operators , n ) ; return 0 ; }