Maximum ways for a boolean expression to evaluate to true.

Solution: Lets say that T(p,q) represents the number of ways operands between p and q evaluate to true and F(p,q) represents the number of ways operands between p and q evaluate to false.

then T(p,q) =

ways for all i between p and q

    if expr[i] is &,   T(p,i-1) * T(i+1,q)

    if expr[i] is |,   T(p,i-1) * T(i+1,q)  +   F(p,i-1) * T(i+1,q) + 
                       T(p,i-1) * F(i+1,q)

    if expr[i] is ^,   F(p,i-1) * T(i+1,q)  +   T(p,i-1) * F(i+1,q)

and F(p,q) =

ways for all i between p and q

    if expr[i] is &,   F(p,i-1) * F(i+1,q)  +  F(p,i-1) * T(i+1,q)  + 
                       T(p,i-1) * F(i+1,q)

    if expr[i] is |,   F(p,i-1) * F(i+1,q) 

    if expr[i] is ^,   F(p,i-1) * F(i+1,q) + T(p,i-1) * T(i+1,q)

 

// the below code is written in C++

#include<bits/stdc++.h>
using namespace std;

// t[i][j] and f[i][j] represents total number of ways the subexpression (expr from i t0 // j) can be evaluated to true and false resp.
int t[100][100],f[100][100];

int falseWays(string s,int p,int q);
int trueWays(string s,int p,int q)
{
if(p>q)
return 0;

if(p==q) return s[p]=='T';

if(t[p][q]!=-1)
return t[p][q];

int ways=0;
int i;

for(i=p;i<=q;i++)
{
if(s[i]=='|')
{
ways+=trueWays(s,p,i-1)*trueWays(s,i+1,q) +
      trueWays(s,p,i-1)*falseWays(s,i+1,q) +
      falseWays(s,p,i-1)*trueWays(s,i+1,q);
}

if(s[i]=='&')
{
ways+=trueWays(s,p,i-1)*trueWays(s,i+1,q);
}

if(s[i]=='^')
{
ways+=trueWays(s,p,i-1)*falseWays(s,i+1,q)+
      falseWays(s,p,i-1)*trueWays(s,i+1,q);
}
}

t[p][q]=ways;
return ways;
}

int falseWays(string s,int p,int q)
{
if(p>q)
return 0;

if(p==q) return s[p]=='F';

if(f[p][q]!=-1)
return f[p][q];

int ways=0;
int i;

for(i=p;i<=q;i++)
{
if(s[i]=='|')
{
ways+=falseWays(s,p,i-1)*falseWays(s,i+1,q);
}

if(s[i]=='&')
{
ways+=falseWays(s,p,i-1)*falseWays(s,i+1,q) +
      trueWays(s,p,i-1)*falseWays(s,i+1,q) +
      falseWays(s,p,i-1)*trueWays(s,i+1,q);
}

if(s[i]=='^')
{
ways+=falseWays(s,p,i-1)*falseWays(s,i+1,q) +
      trueWays(s,p,i-1)*trueWays(s,i+1,q);
}
}

f[p][q]=ways;
return ways;
}

int main()
{
string s="T|F&T|T";   // given string.
int i,j;

int l=s.length();     // l is length of given string.

// setting all elements of t and f as -1.
for(i=0;i<=l;i++)
for(j=0;j<=l;j++)
{
t[i][j]=-1;
f[i][j]=-1;
}

cout<<trueWays(s,0,l-1)<<endl;

return 0;
}