Boolean Parenthesization ( EASY || C++)

10074

Q: Given a boolean expression with following symbols.

Symbols
    'T' ---> true 
    'F' ---> false

And following operators filled between symbols

Operators
    &   ---> boolean AND
    |   ---> boolean OR
    ^   ---> boolean XOR

Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.
Eg :

Input: symbol[]    = {T, F, T}
       operator[]  = {^, &}
Output: 2
The given expression is "T ^ F & T", it evaluates true
in two ways "((T ^ F) & T)" and "(T ^ (F & T))"

This problem is related to Matrix Chain Multiplication
This is so since we need to make partitions around the expression in all possibe ways
One thing to note here is that we'll partition the expression in 2 parts i to k-1 and k+1 to j
Our 'k' will be an operator so we increment k always by 2 s that we always get an operator
Here we also need to determine true or false value of a sub expression since that will be required to get the total no of expressions with TRUE value
Eg consider XOR ( ^ )

true ^ false = true
false ^ true = true

Take another example OR

true | false = true;
true | true = true;
false | true = true;

We can see that we require both TRUE and FALSE values to get the total no of TRUE values so we'll take another variable istrue for that
istrue=1 means we need a sub expression with TRUE value
istrue=0 means we need a sub expression with false value
Since 3 variables are changing i,j & istrue , so require a 3 x 3 matrix

Recursive Code

int solve(string str, int i, int j, int istrue)
    {
        if(i>j)return 0;
        if(i==j)
        {  
		     // if istrue==1 & str[i] ='T' it means we required a true and got it so return 1 else return 0
			 // if istrue==0 & str[i] ='F' it means we required a false and got it so return 1 else return 0
			 
            if(istrue)return str[i]=='T';   
            else return str[i]=='F';
        }     
        int ans=0;
        
        for(int k=i+1;k<=j-1;k=k+2)
        {
            int leftT=  solve(str,i,k-1,1);
            int leftF=  solve(str,i,k-1,0);
            int rightT= solve(str,k+1,j,1);
            int rightF= solve(str,k+1,j,0);
         
            if(str[k]=='^')
            {
                if(istrue)
                ans+=(leftT*rightF) + (leftF*rightT);
                else ans+=(leftT*rightT) + (leftF*rightF) ;
            }
            else if(str[k]=='&')
            {
                if(istrue)
                ans+=(leftT*rightT);
                else ans+=(leftT*rightF) + (leftF*rightT) + (leftF*rightF);
            }
            else if(str[k]=='|')
            {
                if(istrue)
                ans+=(leftT*rightF) + (leftF*rightT) + (leftT*rightT);
                else ans+=(leftF*rightF) ;
            }
        }
        return ans;
    }

Memoization

int dp[205][205][2];
    int solve(string str, int i, int j, int istrue)
    {
        if(i>j)return 0;
        if(i==j)
        {
            if(istrue)return str[i]=='T';
            else return str[i]=='F';
        }
        if(dp[i][j][istrue]!=-1)
        return dp[i][j][istrue];
        
        int ans=0;
        
        for(int k=i+1;k<=j-1;k=k+2)
        {
            int leftT,leftF,rightT,rightF;
            
            if(dp[i][k-1][1]==-1)
            leftT=solve(str,i,k-1,1);
            else leftT=dp[i][k-1][1];
            
            if(dp[i][k-1][0]==-1)
            leftF=solve(str,i,k-1,0);
            else leftF=dp[i][k-1][0];
            
            if(dp[k+1][j][1]==-1)
            rightT=solve(str,k+1,j,1);
            else rightT=dp[k+1][j][1];
            
            if(dp[k+1][j][0]==-1)
            rightF=solve(str,k+1,j,0);
            else rightF=dp[k+1][j][0];
            
            if(str[k]=='^')
            {
                if(istrue)
                ans+=(leftT*rightF) + (leftF*rightT);
                else ans+=(leftT*rightT) + (leftF*rightF) ;
            }
            else if(str[k]=='&')
            {
                if(istrue)
                ans+=(leftT*rightT);
                else ans+=(leftT*rightF) + (leftF*rightT) + (leftF*rightF);
            }
            else if(str[k]=='|')
            {
                if(istrue)
                ans+=(leftT*rightF) + (leftF*rightT) + (leftT*rightT);
                else ans+=(leftF*rightF) ;
            }
            dp[i][j][istrue]=ans%1003;
        }
        return ans%1003;
    }
    int countWays(int N, string S){
        
        memset(dp,-1,sizeof(dp));;
        return solve(S,0,N-1,1);
    }

Comments (12)