Maximum ways for a boolean expression to evaluate to true - PrismoSkills

Maximum ways for a boolean expression to evaluate to true - PrismoSkills
Problem: Given an array of True/False operands and another array of operators, find out the
number of ways parenthesis can be used to group these operands such that the result is always true.

Operators will always be either of these: &, |, ^ (AND, OR or XOR)
Example 1:
Operands = [T, F, F]
Operators = [ |, ^ ]

Then the above can be parenthesized in the following ways to get true:
T | (F ^ F)
(T | F) ^ F
http://www.geeksforgeeks.org/dynamic-programming-set-37-boolean-parenthesization-problem/

Let T(i, j) represents the number of ways to parenthesize the symbols between i and j (both inclusive) such that the subexpression between i and j evaluates to true.

Let F(i, j) represents the number of ways to parenthesize the symbols between i and j (both inclusive) such that the subexpression between i and j evaluates to false.

Base Cases:

T(i, i) = 1 if symbol[i] = 'T' 
T(i, i) = 0 if symbol[i] = 'F' 

F(i, i) = 1 if symbol[i] = 'F' 
F(i, i) = 0 if symbol[i] = 'T'

Time Complexity: O(n³)
Auxiliary Space: O(n²)
Java Code:

1. public int countBoolParenth(char[] symbols, char[] operators) {  
2.     int n = symbols.length;  
3.     int[][] T = new int[n][n];  
4.     int[][] F = new int[n][n];  
5.   
6.     for (int i = 0; i < n; i++) {  
7.         T[i][i] = symbols[i] == 'T' ? 1 : 0;  
8.         F[i][i] = symbols[i] == 'F' ? 1 : 0;  
9.     }  
10.   
11.     for (int w = 2; w <= n; w++) { // w: the width of the sliding window, [2, n]  
12.         for (int i = 0, j = w-1; j < n; i++, j++) { // i..j: the sliding window, [i, j]  
13.             for (int k = i; k < j; k++) { // k: the index of operator to be inserted into symbols  
14.                 // Store Total[i][k] and Total[k+1][j]  
15.                 int tik = T[i][k] + F[i][k];  
16.                 int tkj = T[k + 1][j] + F[k + 1][j];  
17.   
18.                 // Follow the recursive formulas according to the current operator  
19.                 if (operators[k] == '&') {  
20.                     T[i][j] += T[i][k] * T[k + 1][j];  
21.                     F[i][j] += (tik * tkj - T[i][k] * T[k + 1][j]);  
22.                 }  
23.   
24.                 if (operators[k] == '|') {  
25.                     F[i][j] += F[i][k] * F[k + 1][j];  
26.                     T[i][j] += (tik * tkj - F[i][k] * F[k + 1][j]);  
27.                 }  
28.   
29.                 if (operators[k] == '^') {  
30.                     T[i][j] += F[i][k] * T[k + 1][j] + T[i][k] * F[k + 1][j];  
31.                     F[i][j] += T[i][k] * T[k + 1][j] + F[i][k] * F[k + 1][j];  
32.                 }  
33.             }  
34.         }  
35.     }  
36.     return T[0][n - 1];  
37. } 

int countParenth(char symb[], char oper[], int n)

{

    int F[n][n], T[n][n];

    // Fill diaginal entries first

    // All diagonal entries in T[i][i] are 1 if symbol[i]

    // is T (true).  Similarly, all F[i][i] entries are 1 if

    // symbol[i] is F (False)

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

    {

        F[i][i] = (symb[i] == 'F')? 1: 0;

        T[i][i] = (symb[i] == 'T')? 1: 0;

    }

    // Now fill T[i][i+1], T[i][i+2], T[i][i+3]... in order

    // And F[i][i+1], F[i][i+2], F[i][i+3]... in order

    for (int gap=1; gap<n; ++gap)

    {

        for (int i=0, j=gap; j<n; ++i, ++j)

        {

            T[i][j] = F[i][j] = 0;

            for (int g=0; g<gap; g++)

            {

                // Find place of parenthesization using current value

                // of gap

                int k = i + g;

                // Store Total[i][k] and Total[k+1][j]

                int tik = T[i][k] + F[i][k];

                int tkj = T[k+1][j] + F[k+1][j];

                // Follow the recursive formulas according to the current

                // operator

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

                {

                    T[i][j] += T[i][k]*T[k+1][j];

                    F[i][j] += (tik*tkj - T[i][k]*T[k+1][j]);

                }

                if (oper[k] == '|')

                {

                    F[i][j] += F[i][k]*F[k+1][j];

                    T[i][j] += (tik*tkj - F[i][k]*F[k+1][j]);

                }

                if (oper[k] == '^')

                {

                    T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j];

                    F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j];

                }

            }

        }

    }

    return T[0][n-1];

}

int n = operands.length;

int T[n][n];
int F[n][n];

for (int i=0; i&lt;n; i++)
{
    F[i][i] = (symb[i] == 'F')? 1: 0;
    T[i][i] = (symb[i] == 'T')? 1: 0;
}
 
for (int gap=1; gap&lt;n; gap++) // loop required to fill whole of the matrices T and F
{
    for (int i=0, j=gap; j&lt;n; i++, j++) // vary i,j from 0 to n
    {
        T[i][j] = F[i][j] = 0;
        for (int k=i; k&lt;j; k++) // vary k from i to j
        {
            // above equations
        }
    }
}

return T[0][n-1];
Read full article from Maximum ways for a boolean expression to evaluate to true - PrismoSkills