Boolean Parenthesization Problem | DP |  ; 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 ) )
using System ; class GFG { static int parenthesis_count ( string str , int i , int j , int isTrue , int [ , , ] dp ) { if ( i > j ) return 0 ; if ( i == j ) { if ( isTrue == 1 ) { return ( str [ i ] == ' T ' ) ? 1 : 0 ; } else { return ( str [ i ] == ' F ' ) ? 1 : 0 ; } } if ( dp [ i , j , isTrue ] != - 1 ) return dp [ i , j , isTrue ] ; int temp_ans = 0 ; int leftTrue , rightTrue , leftFalse , rightFalse ; for ( int k = i + 1 ; k <= j - 1 ; k = k + 2 ) { if ( dp [ i , k - 1 , 1 ] != - 1 ) leftTrue = dp [ i , k - 1 , 1 ] ; else { leftTrue = parenthesis_count ( str , i , k - 1 , 1 , dp ) ; } if ( dp [ i , k - 1 , 0 ] != - 1 ) leftFalse = dp [ i , k - 1 , 0 ] ; else { leftFalse = parenthesis_count ( str , i , k - 1 , 0 , dp ) ; } if ( dp [ k + 1 , j , 1 ] != - 1 ) rightTrue = dp [ k + 1 , j , 1 ] ; else { rightTrue = parenthesis_count ( str , k + 1 , j , 1 , dp ) ; } if ( dp [ k + 1 , j , 0 ] != - 1 ) rightFalse = dp [ k + 1 , j , 0 ] ; else { rightFalse = parenthesis_count ( str , k + 1 , j , 0 , dp ) ; } if ( str [ k ] == ' & ' ) { if ( isTrue == 1 ) { temp_ans = temp_ans + leftTrue * rightTrue ; } else { temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse ; } } else if ( str [ k ] == ' ▁ ' ) { if ( isTrue == 1 ) { temp_ans = temp_ans + leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue ; } else { temp_ans = temp_ans + leftFalse * rightFalse ; } } else if ( str [ k ] == ' ^ ' ) { if ( isTrue == 1 ) { temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue ; } else { temp_ans = temp_ans + leftTrue * rightTrue + leftFalse * rightFalse ; } } dp [ i , j , isTrue ] = temp_ans ; } return temp_ans ; } static int countWays ( int N , string S ) { int [ , , ] dp = new int [ N + 1 , N + 1 , 2 ] ; for ( int i = 0 ; i < ( N + 1 ) ; i ++ ) { for ( int j = 0 ; j < ( N + 1 ) ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) { dp [ i , j , k ] = - 1 ; } } } return parenthesis_count ( S , 0 , N - 1 , 1 , dp ) ; } static void Main ( ) { string symbols = " TTFT " ; string operators = " | & ^ " ; string S = " " ; int j = 0 ; for ( int i = 0 ; i < symbols . Length ; i ++ ) { S = S + symbols [ i ] ; if ( j < operators . Length ) S = S + operators [ j ++ ] ; } int N = S . Length ; Console . WriteLine ( countWays ( N , S ) ) ; } }