Make delicious recipes!

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


Example 2:

Operands = [T, F, F, T]
Operators = [ |, ^, & ]

Ways to generate true:
(T | (F ^ F))&T
((T | F) ^ F)&T


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];


Reference: http://people.cs.clemson.edu/~bcdean/dp_practice/dp_9.swf

In terms of loops, note how similar this problem is to:
  1. Longest palindrome creation
  2. Optimum matrix chain multiplication
All of these problems have an outer loop which starts with 1 or 2 elements and then gradually widens the scope of the problem being solved.







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal