Problem Statement

Given a boolean expression S of length N with following symbols.Symbols    'T' ---> true    'F' ---> falseand following operators filled between symbolsOperators    &   ---> 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.

Example 1:

Input: N = 7
S = T|T&F^T
Output: 4
Explaination: The expression evaluates
to true in 4 ways ((T|T)&(F^T)),
(T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)).

Problem Link

Reference Videos

https://www.youtube.com/watch?v=JbRsM2X2_pg&ab_channel=Pepcoding

Code

//Using Bottom-Up DP

class Solution{
public:
    int countWays(int N, string S){
        
        string oprt = "", oprn = "";
        
        for(char ch:S) {
            if(ch=='T'||ch=='F')
            oprn+=ch;
            else
            oprt+=ch;
        }
        
        int n = oprn.size();
        
        vector<vector<int>> dpt(n,vector<int>**(n,0**));
        vector<vector<int>> dpf(n,vector<int>**(n,0**));
        
        for(int gap=0;gap<n;gap++) {
            for(int i=0,j=gap;j<n;i++,j++) {
               
                if(gap==0)
                {
                    if(oprn[i]=='T')
                    {
                        dpt[i][j] = 1;
                        dpf[i][j] = 0;
                    }
                    else
                    {
                        dpt[i][j] = 0;
                        dpf[i][j] = 1;
                    }
                }
            
                else {
                       for(int k=i;k<j;k++) {
                           char op = oprt[k];
                           int ltc = dpt[i][k];
                           int rtc = dpt[k+1][j];
                           int lfc = dpf[i][k];
                           int rfc = dpf[k+1][j];
                           
                           if(op=='&') {
                               dpt[i][j]+= (ltc*rtc)% 1003;
                               dpf[i][j]+= (ltc*rfc + lfc*rtc + lfc*rfc)% 1003;
                           }
                           else if(op=='|') {
                               dpt[i][j]+= (ltc*rfc + lfc*rtc + ltc*rtc)% 1003;
                               dpf[i][j]+= (lfc*rfc)% 1003;
                           }
                           else {
                               dpt[i][j]+= (ltc*rfc + lfc*rtc)% 1003 ;
                               dpf[i][j]+= (lfc*rfc + ltc*rtc)% 1003;
                           }
                       }
               
                }
            }
        }
      
        return dpt[0][n-1] % 1003; 
    }
};
// Time Complexity : O(n^3),   Space Complexity : O(n^2)