Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Boolean Evaluation

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
154 upvotes
Asked in companies
SliceIntuitAmazon

Problem statement

You are given an expression 'exp' in the form of a string where operands will be : (TRUE or FALSE), and operators will be : (AND, OR or XOR).


Now you have to find the number of ways we can parenthesize the expression such that it will evaluate to TRUE.


As the answer can be very large, return the output modulo 1000000007.


Note :

‘T’ will represent the operand TRUE.
‘F’ will represent the operand FALSE.
‘|’ will represent the operator OR.
‘&’ will represent the operator AND.
‘^’ will represent the operator XOR.

Example :

Input: 'exp’ = "T|T & F".

Output: 1

Explanation:
There are total 2  ways to parenthesize this expression:
    (i) (T | T) & (F) = F
    (ii) (T) | (T & F) = T
Out of 2 ways, one will result in True, so we will return 1.
Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of each input contains a string representing the expression ‘exp’.

Output format:

print a single integer representing the number of ways we can parenthesize the expression to evaluate to true.   
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1 :

T^T^F    

Sample Output 1 :

0

Explanation For Sample Input 1:

There are total 2  ways to parenthesize this expression:
(i) (T^T)^(F) = F
(ii) (T)^(T^F) = F
Both ways will result in False, so we will return 0.
Sample Input 2 :
F|T^F
Sample Output 2 :
2

Explanation For Sample Input 2:

For the first test case:
There are total 2  ways to parenthesize this expression:
(i) (F|T)^(F) = T
(ii) (F)|(T^F) = T
Both ways will result in True, so we will return 2.

Expected time complexity

The expected time complexity is O(n ^ 3), where 'n' denotes the length of 'exp'.

Constraints:

3 <= |‘exp’| <= 200
Where |'exp'| denotes the length of 'exp'.

Time Limit: 1 sec
Hint

 Can you try to think to find all combinations and then calculate?

Approaches (3)
Recursion Approach

Approach: Basically, we will divide the expression into smaller parts and will try to find the number of ways a smaller expression can result in True and the number of ways a smaller expression can result in False.

 

With the help of the result of the smaller expression, we will be able to find the number of ways the whole expression can result in True.

 

Let’s define a recursive function, ‘findWays’, which will receive the following parameter.

(i) ‘exp’ the given expression.

(ii) ‘st’ is an integer variable representing the starting point for the sub-expression.

(iii) ‘end’ is an integer variable representing the ending point for the sub-expression.

(iii) ‘isTrue’ is a bool variable representing whether the sub-expression should evaluate to True or False.

 

Base Condition :

  1. If  ‘st’ >  ‘end’ then do:
    • Return False.
  2. If  ‘st’ is equal to  ‘end’ then do:
    • If ‘isTrue’  is equal to True :
      • If current element is true or ‘exp[st]’ == ‘T’
        • Return True
      • Else
        • Return False.
    • If ‘isTrue’  is equal to False :
      • If current element is False or ‘exp[st]’ == ‘F’
        • Return True.
      • Else
        • Return False.

Recursive Calls:

  1. Initialize an integer variable ‘ans’=0.
  2. Run a loop over ‘exp’ for ‘st’+1 <= ‘k’ <= 'end’-1 and do:
    • We will need to find out the value of the below variables
    • ‘leftTrue’  = The number of ways the expression left to ‘k’ will be true.
    • ‘leftFalse’  = The number of ways the expression left to ‘k’ will be false.
    • ‘rightTrue’  = The number of ways expression right to ‘k’ will be true:
    • ‘rightFalse’  = The number of ways expression right to ‘k’ will be true:
    • We will find these values by making calls to ‘findWays'.
    • To make a call to the left part,  ‘st’ will be ‘st’, and  ‘end’ will be ‘k’-1.
    • To make a call to the right part, ‘st’ will be ‘k’+1, and ‘end’ will be ‘end’.
    • Set the value of ‘isTrue’ = True if we need to find out the number of ways for true else, set False.
  3. Now there will be many combinations according to the value of ‘isTrue’ and the value of the current operator(‘exp[k]’).
  4. Let’s find out what value will current sub-expression add to ‘ans’ for the given operator ‘|’ and ‘isTrue’ = True.
  5. The truth table for OR :
    • T|T=T
    • F|T=T
    • T|F=T
    • F|F=F
  6. So ‘ans’+= ‘leftTrue’*‘rightFalse’ +‘leftFalse’ *‘rightTrue’ +‘leftTrue’*‘rightTrue’
  7. Similarly, we can find’ for other operators.
  8. Return ‘ans’.
Time Complexity

O(4^n), where ‘n’ is the size of the string.

 

As in each step, we are making 4 recursive calls till the value of ‘n’ for the current call is greater than 1, thus raising the time complexity to O(4^n).

 

Hence the final time complexity is O(4^n).

Space Complexity

O(4^n), where ‘n’ is the size of the string.

 

This will be the space the recursion stack uses to save 4^'n' calls.

 

Hence the final space complexity is O(4^n).

Code Solution
(100% EXP penalty)
Boolean Evaluation
All tags
Sort by
Search icon

Interview problems

EASY DP TABULATION✅✅✅

#include <bits/stdc++.h>

#define MOD 1000000007

 

int evaluateExp(string &exp) {

  int n = exp.size();

  vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, 0)));

 

  for (int i = 0; i < n; ++i) {

    if (exp[i] == 'T') {

      dp[i][i][1] = 1;

      dp[i][i][0] = 0;

    } else if (exp[i] == 'F') {

      dp[i][i][0] = 1;

      dp[i][i][1] = 0;

    }

  }

 

  for (int len = 2; len <= n; len++) {

    for (int i = 0; i <= n - len; i++) {

      int j = i + len - 1;

      for (int k = i + 1; k < j; k += 2) {

        int LT = dp[i][k - 1][1];

        int LF = dp[i][k - 1][0];

        int RT = dp[k + 1][j][1];

        int RF = dp[k + 1][j][0];

 

        if (exp[k] == '&') {

          dp[i][j][1] = (dp[i][j][1] + 1LL * LT * RT % MOD) % MOD;

          dp[i][j][0] = (dp[i][j][0] + 1LL * LT * RF % MOD +

                         1LL * LF * RT % MOD + 1LL * LF * RF % MOD) %

                        MOD;

        }

 

        if (exp[k] == '|') {

          dp[i][j][1] = (dp[i][j][1] + 1LL * LT * RT % MOD +

                         1LL * LT * RF % MOD + 1LL * RT * LF % MOD) %

                        MOD;

          dp[i][j][0] = (dp[i][j][0] + 1LL * LF * RF % MOD) % MOD;

        }

 

        if (exp[k] == '^') {

          dp[i][j][1] =

              (dp[i][j][1] + 1LL * LT * RF % MOD + 1LL * RT * LF % MOD) % MOD;

          dp[i][j][0] =

              (dp[i][j][0] + 1LL * LF * RF % MOD + 1LL * RT * LT % MOD) % MOD;

        }

      }

    }

  }

 

  return dp[0][n - 1][1];

}

 

18 views
0 replies
0 upvotes

Interview problems

C ++ || Striver's || Tabulation

int evaluateExp(string & exp) {

    

    int n = exp.size();

    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n + 1, vector<ll>(2, 0)));

 

    for(int i=n-1; i>=0; i--){

 

        for(int j=0; j<n; j++){

 

            for(int isTrue=0; isTrue<=1; isTrue++){

 

                // Single element

                if(i == j){

                    if(isTrue) dp[i][j][isTrue] = exp[i] == 'T';

                    else dp[i][j][isTrue] = exp[i] == 'F';

                    continue;

                }

 

                ll ways = 0;

                for(int ind=i+1; ind<=j-1; ind+=2){

            

                    ll lT = dp[i][ind - 1][1];

                    ll lF = dp[i][ind - 1][0];

                    ll rT = dp[ind + 1][j][1];

                    ll rF = dp[ind + 1][j][0];

            

                    if(exp[ind] == '&'){

            

                        if(isTrue) ways = (ways + (lT * rT) % mod) % mod;

                        else ways = (ways + (lT * rF) % mod + (lF * rT) % mod + (lF * rF) % mod) % mod;

            

                    }

                    else if(exp[ind] == '|'){

                        if(isTrue) ways = (ways + (lT * rF)% mod + (lF * rT)% mod + (lT * rT)%mod)% mod;

                        else ways = (ways + (lF * rF)% mod) % mod;

                    }

                    else{

                        if(isTrue) ways = (ways + (lT  * rF)% mod + (lF * rT)% mod)% mod;

                        else ways = (ways + (lT * rT)% mod + (lF * rF)% mod)% mod;

                    }

            

                }

            

                dp[i][j][isTrue] = ways;

 

            }

 

        }

 

    }

 

    return dp[0][n - 1][1];

 

}

214 views
0 replies
1 upvote

Interview problems

Why only 25 testcases are passing?

#include <bits/stdc++.h>

#define MOD 1000000007

long long solve(int i, int j, int isTrue, string &exp, vector<vector<vector<long long>>> &dp){

    if(i>j)

        return 0;

   

    if(i == j){

        if(isTrue)

            return (exp[i] == 'T');

       

        else

            return (exp[i] == 'F');

    }

    if(dp[i][j][isTrue] != -1)

        return dp[i][j][isTrue];

       

    long long ways = 0;

    for(int ind=i+1; ind<=j-1; ind = ind+2){

        int ltp = solve(i, ind-1, 1, exp, dp);

        int lfp = solve(i, ind-1, 0, exp, dp);

        int rtp = solve(ind+1, j, 1, exp, dp);

        int rfp = solve(ind+1, j, 0, exp, dp);

        if(exp[ind] == '&'){

            if(isTrue)

                ways = (ways + (ltp*rtp)%MOD)%MOD;

            else

                ways = (ways + (ltp*rfp)%MOD + (lfp*rtp)%MOD + (lfp*rfp)%MOD)%MOD;

        }

        else if(exp[ind] == '|'){

            if(isTrue)

                ways = (ways + (ltp*rtp)%MOD + (ltp*rfp)%MOD + (lfp*rtp)%MOD)%MOD;

           

            else

                ways = (ways + (lfp*rfp)%MOD)%MOD;

        }

        else{

            if(isTrue)

                ways = (ways + (ltp*rfp)%MOD + (lfp*rtp)%MOD)%MOD;

           

            else

                ways = (ways + (ltp*rtp)%MOD + (lfp*rfp)%MOD)%MOD;

        }

    }

    return dp[i][j][isTrue] = ways%MOD;

}

int evaluateExp(string & exp) {

   

    int n = exp.length();

    vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(n, vector<long long>(2, -1)));

   

    return solve(0, n-1, 1, exp, dp);

}

107 views
1 reply
1 upvote

Interview problems

Easy Recursion + Tabulation

int MOD = 1000000007;

#define ll long long

int dfs(string &s, int i, int j, int isTrue)

{

    if (i > j)

        return 0;

    if (i == j)

    {

        if (isTrue)

            return s[i] == 'T';

        else

            return s[i] == 'F';

    }

 

    long long int ways = 0;

    for (int k = i + 1; k <= j; k += 2)

    {

        int lt = dfs(s, i, k - 1, 1);

        int lf = dfs(s, i, k - 1, 0);

        int rt = dfs(s, k + 1, j, 1);

        int rf = dfs(s, k + 1, j, 0);

 

        if (s[k] == '&')

        {

            if (isTrue)

                ways = (ways + (lt * rt) % MOD) % MOD;

            else

                ways = (ways + (lf * rt + lt * rf + lf * rf) % MOD) % MOD;

        }

        else if (s[k] == '|')

        {

            if (isTrue)

                ways = (ways + (lt * rt + lf * rt + lt * rf) % MOD) % MOD;

            else

                ways = (ways + (lf * rf) % MOD) % MOD;

        }

        else if (s[k] == '^')

        {

            if (isTrue)

                ways = (ways + (lt * rf + lf * rt) % MOD) % MOD;

            else

                ways = (ways + (lt * rt + lf * rf) % MOD) % MOD;

        }

    }

 

    return ways % MOD;

}

 

int evaluateExp(string &s)

{

    ll n = s.size();

    // return dfs(s, 0, n - 1, 1);

    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(2, -1)));

    for (ll i = n - 1; i >= 0; i--)

    {

        for (ll j = 0; j < n; j++)

        {

            if (i > j)

                continue;

            for (int isTrue = 0; isTrue <= 1; isTrue++)

            {

                if (i == j)

                {

                    if (isTrue == 1)

                        dp[i][j][isTrue] = s[i] == 'T';

                    else

                        dp[i][j][isTrue] = s[i] == 'F';

                    continue;

                }

                long long int ways = 0;

                for (ll k = i; k < j; k++)

                {

                    ll lt = dp[i][k - 1][1];

                    ll lf = dp[i][k - 1][0];

                    ll rt = dp[k + 1][j][1];

                    ll rf = dp[k + 1][j][0];

 

                    if (s[k] == '&')

                    {

                        if (isTrue)

                            ways = (ways + (lt * rt) % MOD) % MOD;

                        else

                            ways = (ways + (lf * rt + lt * rf + lf * rf) % MOD) % MOD;

                    }

                    else if (s[k] == '|')

                    {

                        if (isTrue)

                            ways = (ways + ((lt * rt) % MOD + (lf * rt) % MOD + (lt * rf) % MOD) % MOD) % MOD;

                        else

                            ways = (ways + (lf * rf) % MOD) % MOD;

                    }

                    else if (s[k] == '^')

                    {

                        if (isTrue)

                            ways = (ways + ((lt * rf) % MOD + (lf * rt) % MOD) % MOD) % MOD;

                        else

                            ways = (ways + ((lt * rt) % MOD + (lf * rf) % MOD) % MOD) % MOD;

                    }

                }

                dp[i][j][isTrue] = ways % MOD;

            }

        }

    }

    return dp[0][n - 1][1];

}

201 views
0 replies
0 upvotes

Interview problems

Passing Only 25/50. Can anyone tell me why?

const int MOD = 1e9 + 7;

 

int evaluateExp(string & exp) {

    // Write your code here.

    int n = exp.size();

    if(n<3){

        if(exp[0]=='T') return 1;

        else return 0;

    }

 

    string operand  = "";

    string operators = "";

    for(int i=0; i<n; i++){

        if(exp[i]=='T' || exp[i]=='F'){

            operand += exp[i];

        }else{

            operators += exp[i];

        }

    }

 

    n = operand.size();

    int m = operators.size();

    vector<vector<pair<int,int>>> DP(n, vector<pair<int,int>>(n, {0,0}));

    for(int i=0; i<n; i++){

        if(operand[i]=='T'){

            DP[i][i] = {1,0};

        }else if(operand[i]=='F'){

            DP[i][i] = {0,1};

        }

    }

    for(int length = 2; length<=n; length++){

        for(int i = 0; i+length-1<n; i++){

            int j = i + length - 1;

            for(int k=i; k<j; k++){

                if (operators[k] == '&') {

                    DP[i][j].first = (DP[i][j].first + ((DP[i][k].first * DP[k + 1][j].first) % MOD)) % MOD;

                    DP[i][j].second = (DP[i][j].second + ((((DP[i][k].second * DP[k + 1][j].second) % MOD) +

                                                            ((DP[i][k].second * DP[k + 1][j].first) % MOD) +

                                                            ((DP[i][k].first * DP[k + 1][j].second) % MOD)) % MOD)) % MOD;

                } else if (operators[k] == '|') {

                    DP[i][j].first = (DP[i][j].first + ((((DP[i][k].first * DP[k + 1][j].first) % MOD) +

                                                         ((DP[i][k].second * DP[k + 1][j].first) % MOD) +

                                                         ((DP[i][k].first * DP[k + 1][j].second) % MOD)) % MOD)) % MOD;

                    DP[i][j].second = (DP[i][j].second + ((DP[i][k].second * DP[k + 1][j].second) % MOD)) % MOD;

                } else if (operators[k] == '^') {

                    DP[i][j].first = (DP[i][j].first + ((((DP[i][k].first * DP[k + 1][j].second) % MOD) +

                                                         ((DP[i][k].second * DP[k + 1][j].first) % MOD)) % MOD)) % MOD;

                    DP[i][j].second = (DP[i][j].second + ((((DP[i][k].second * DP[k + 1][j].second) % MOD) +

                                                           ((DP[i][k].first * DP[k + 1][j].first) % MOD)) % MOD)) % MOD;

                }

            }

        }

    }

    return DP[0][n-1].first;

}

214 views
3 replies
1 upvote

Interview problems

C++

int M = 1e9 + 7;
long long f(int i, int j, int isTrue, string& s,
            vector<vector<vector<int>>>& dp) {
    if (i > j)
        return 0;
    if (i == j) {
        if (isTrue)
            return s[i] == 'T';
        else
            return s[i] == 'F';
    }
    if (dp[i][j][isTrue] != -1)
        return dp[i][j][isTrue];
    long long ans = 0;
    for (int ind = i + 1; ind <= j - 1; ind += 2) {
        long long lT = f(i, ind - 1, 1, s, dp);
        long long lF = f(i, ind - 1, 0, s, dp);
        long long rT = f(ind + 1, j, 1, s, dp);
        long long rF = f(ind + 1, j, 0, s, dp);
        if (s[ind] == '&') {
            if (isTrue)
                ans = (ans + (lT * rT) % M) % M;
            else
                ans = (ans + (rT * lF) % M + (rF * lT) % M + (rF * lF) % M) % M;
        } else if (s[ind] == '|') {
            if (isTrue) {
                ans = (ans + (lT * rT) % M + (lT * rF) % M + (lF * rT) % M) % M;
            } else
                ans = (ans + (rF * lF) % M) % M;
        } else {
            if (isTrue) {
                ans = (ans + (lT * rF) % M + (lF * rT) % M) % M;
            } else {
                ans = (ans + (lT * rT) % M + (lF * rF) % M) % M;
            }
        }
    }
    return dp[i][j][isTrue] = ans % M;
}
int evaluateExp(string& s) {
    int n = s.size();
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(n + 1, vector<int>(2, -1)));
    return f(0, s.size() - 1, 1, s, dp);
}
293 views
0 replies
0 upvotes

Interview problems

C++ Tabulaton Solution

const int mod = 1000000007;

int evaluateExp(string & exp) {
    // Write your code here.
    int n = exp.size();
    vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(n, vector<long long>(2, 0)));

    // return f(0,n-1, 1, exp, dp);
    for(int i=n-1; i>=0; i--) {
        for(int j=0; j<n; j++) {
            if(i>j) continue;
            for(int isTrue=0; isTrue<=1; isTrue++) {
                if (i == j) {
                    if (isTrue == 1) dp[i][j][isTrue] = exp[i] == 'T';
                    else dp[i][j][isTrue] = exp[i] == 'F';
                    continue;
                }

                long long ways = 0;
                for(int k=i; k<j; k++) {
                    long long leftTrue = dp[i][k-1][1];
                    long long leftFalse = dp[i][k-1][0];
                    long long rightTrue = dp[k+1][j][1];
                    long long rightFalse = dp[k+1][j][0];

                    if(exp[k] == '&') {
                        if(isTrue) ways = (ways + (leftTrue*rightTrue)%mod)%mod;
                        else ways = (ways + (leftFalse*rightTrue)%mod + (leftFalse*rightFalse)%mod + (leftTrue*rightFalse)%mod)%mod;
                    }
                    else if(exp[k] == '|') {
                        if(isTrue) ways = (ways + (leftTrue*rightTrue)%mod + (leftTrue*rightFalse)%mod + (leftFalse*rightTrue)%mod)%mod;
                        else ways = (ways + (leftFalse*rightFalse)%mod)%mod;
                    }
                    else {
                        if(isTrue) ways = (ways + (leftTrue*rightFalse)%mod + (leftFalse*rightTrue)%mod)%mod;
                        else ways = (ways + (leftTrue*rightTrue)%mod + (leftFalse*rightFalse)%mod)%mod;
                    }
                }

                dp[i][j][isTrue] = ways;
            }
        }
    }

    return dp[0][n-1][1];
}
217 views
0 replies
0 upvotes

Interview problems

C++ Memoization DP

const int mod = 1000000007;
int f(int i, int j, int isTrue, string& s, vector<vector<vector<long long>>>& dp) {
    if(i>j) return 0;
    if(i==j) {
        if(isTrue) return s[i]=='T';
        else return s[i] == 'F';
    }
    if(dp[i][j][isTrue] != -1) return dp[i][j][isTrue];

    long long ways = 0;
    for(int k=i; k<j; k++) {
        long long leftTrue = f(i, k-1, 1, s, dp);
        long long leftFalse = f(i, k-1, 0, s, dp);
        long long rightTrue = f(k+1, j, 1, s, dp);
        long long rightFalse = f(k+1, j, 0, s, dp);

        if(s[k] == '&') {
            if(isTrue) ways = (ways + (leftTrue*rightTrue)%mod)%mod;
            else ways = (ways + (leftFalse*rightTrue)%mod + (leftFalse*rightFalse)%mod + (leftTrue*rightFalse)%mod)%mod;
        }
        else if(s[k] == '|') {
            if(isTrue) ways = (ways + (leftTrue*rightTrue)%mod + (leftTrue*rightFalse)%mod + (leftFalse*rightTrue)%mod)%mod;
            else ways = (ways + (leftFalse*rightFalse)%mod)%mod;
        }
        else {
            if(isTrue) ways = (ways + (leftTrue*rightFalse)%mod + (leftFalse*rightTrue)%mod)%mod;
            else ways = (ways + (leftTrue*rightTrue)%mod + (leftFalse*rightFalse)%mod)%mod;
        }
    }

    return dp[i][j][isTrue] = ways;
}

int evaluateExp(string & exp) {
    // Write your code here.
    int n = exp.size();
    vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(n, vector<long long>(2, -1)));

    return f(0,n-1, 1, exp, dp);
}
272 views
0 replies
0 upvotes

Interview problems

Using Tabulation

#define mod 1000000007

#include <bits/stdc++.h>

 

int evaluateExp(string & exp) {

    int n = exp.size();

    vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(n, vector<long long>(2, 0)));

    // return f(0, n-1, 1, exp, dp);

 

    for(int i = n-1; i >= 0; i--){

        for(int j = i; j < n; j++){

            for(int isTrue = 0; isTrue <= 1; isTrue++){

 

                if(i == j){

                    if(isTrue == 1) dp[i][j][isTrue] = exp[i] == 'T';

 

                    else dp[i][j][isTrue] = exp[i] == 'F';

                }

                else{

                    long long ways = 0;

 

                    for(int ind = i+1; ind <= j-1; ind += 2){

                        long long lT = dp[i][ind-1][1];

                        long long lF = dp[i][ind-1][0];

                        long long rT = dp[ind+1][j][1];

                        long long rF = dp[ind+1][j][0];

 

                        if(exp[ind] == '&'){

                            if(isTrue) ways = (ways + (rT * lT)%mod)%mod;

 

                            else ways = (ways + ((rT * lF)%mod + (rF * lT)%mod + (rF * lF)%mod)%mod)%mod;

                        }

                        else if(exp[ind] == '|'){

                            if(isTrue) ways = (ways + ((lT * rT)%mod + (lT * rF)%mod + (lF * rT)%mod)%mod)%mod;

 

                            else ways = (ways + (rF * lF)%mod)%mod;

                        }

                        else{

                            if(isTrue) ways = (ways + (lT * rF)%mod + (lF * rT)%mod)%mod;

 

                            else ways = (ways + (lT * rT)%mod + (lF * rF)%mod)%mod;

                        }

                    }

 

                    dp[i][j][isTrue] = ways;

                }

            }

        }

    }

 

    return dp[0][n-1][1];

}

209 views
0 replies
2 upvotes

Interview problems

C++ Solution using Tabulation

#include <bits/stdc++.h> 

int evaluateExp(string &s) 

{

    int mod = 1000000007;

    int n = s.length();

    vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(n+1,vector<int>(2,-1)));

    for(int i=0; i<n; i++) 

    {

        if(s[i]=='T')

        {

            dp[i][i][1]=1;

            dp[i][i][0]=0;

        }

        else            

        {

            dp[i][i][1]=0;

            dp[i][i][0]=1;

        }

    }

    for(int i=n-1; i>=0; i--) 

    {

        for(int j=i+1; j<n; j++) 

        {

            for(int isTrue=0; isTrue<=1; isTrue++) 

            {

                long ways = 0;

                for(int ind=i+1; ind<=j-1; ind+=2) 

                {

                    long lt = dp[i][ind - 1][1] % mod;

                    long lf = dp[i][ind - 1][0] % mod;

                    long rt = dp[ind + 1][j][1] % mod;

                    long rf = dp[ind + 1][j][0] % mod; 

                    if(s[ind] == '&') 

                    {

                        if(isTrue == 1) 

                        {

                            ways = (ways + (lt * rt) % mod) % mod;

                        }

                        else 

                        {

                            ways = (ways + (rt * lf) % mod + (lt * rf) % mod + (lf * rf) % mod) % mod;

                        }

                    }

                    else if(s[ind] == '|') 

                    {

                        if(isTrue == 1) 

                        {

                            ways = (ways + (lt * rt) % mod + (lt * rf) % mod + (rt * lf) % mod) % mod; 

                        }

                        else 

                        {

                            ways = (ways + (lf * rf) % mod) % mod;

                        }

                    }

                    else if(s[ind] == '^') 

                    {

                        if(isTrue == 1) 

                        {

                            ways = (ways + (lt * rf) % mod + (rt * lf) % mod) % mod;

                        }

                        else 

                        {

                            ways = (ways + (lt * rt) % mod + (lf * rf) % mod) % mod;

                        }

                    }

                }

                dp[i][j][isTrue] = ways;

            }

        }

    }

    return dp[0][n - 1][1];

}

152 views
0 replies
0 upvotes
Full screen
Console