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 ) )
function countWays ( N , S ) { let dp = new Array ( N + 1 ) ; for ( let i = 0 ; i < N + 1 ; i ++ ) { dp [ i ] = new Array ( N + 1 ) ; for ( let j = 0 ; j < N + 1 ; j ++ ) { dp [ i ] [ j ] = new Array ( 2 ) ; for ( let k = 0 ; k < 2 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; } } return parenthesis_count ( S , 0 , N - 1 , 1 , dp ) ; } function parenthesis_count ( str , i , j , isTrue , dp ) { if ( i > j ) return 0 ; if ( i == j ) { if ( isTrue == 1 ) { return ( str [ i ] == ' ' ) ? 1 : 0 ; } else { return ( str [ i ] == ' ' ) ? 1 : 0 ; } } if ( dp [ i ] [ j ] [ isTrue ] != - 1 ) return dp [ i ] [ j ] [ isTrue ] ; let temp_ans = 0 ; let leftTrue , rightTrue , leftFalse , rightFalse ; for ( let 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 ; } let symbols = " " ; let operators = " " ; let S = [ ] ; let j = 0 ; for ( let i = 0 ; i < symbols . length ; i ++ ) { S . push ( symbols [ i ] ) ; if ( j < operators . length ) S . push ( operators [ j ++ ] ) ; } let N = S . length ; document . write ( countWays ( N , S . join ( " " ) ) ) ;