Maximum ways for a boolean expression to evaluate to true
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
Solution:
Lets say that T(i,j) represents the number of ways operands between i and j evaluate to true and
F(i,j) represents the number of ways operands between i and j evaluate to false.
then T(i,j) =
sum() for all k between i and j
if operator[k] is &, T(i,k) * T(k+1,j)
if operator[k] is |, T(i,k) * T(k+1,j) + F(i,k) * T(k+1,j) + T(i,k) * F(k+1,j)
if operator[k] is ^, F(i,k) * T(k+1,j) + T(i,k) * F(k+1,j)
and F(i,j) =
sum() for all k between i and j
if operator[k] is &, F(i,k) * F(k+1,j) + F(i,k) * T(k+1,j) + T(i,k) * F(k+1,j)
if operator[k] is |, F(i,k) * F(k+1,j)
if operator[k] is ^, T(i,k) * T(k+1,j) + F(i,k) * F(k+1,j)
So there are overlapping subproblems here which can be handled efficiently using dynamic programming:
int n = operands.length;
int T[n][n];
int F[n][n];
for (int i=0; i<n; i++)
{
F[i][i] = (symb[i] == 'F')? 1: 0;
T[i][i] = (symb[i] == 'T')? 1: 0;
}
for (int gap=1; gap<n; gap++) // loop required to fill whole of the matrices T and F
{
for (int i=0, j=gap; j<n; i++, j++) // vary i,j from 0 to n
{
T[i][j] = F[i][j] = 0;
for (int k=i; k<j; k++) // vary k from i to j
{
// above equations
}
}
}
return T[0][n-1];
