This is a C++ Program that Solves Counting Boolean Parenthesization Problem using Dynamic Programming technique.
You are given a boolean expression with symbols True and False and operators And, Or and Xor. Find the number of ways in which the expression can be parenthesized so that the value of expression evaluates to true.
The problem can be solved using dynamic programming using the same approach used to solve matrix multiplication problem. First we will solve for all the subexpressions of one symbol, then for subexpressions of two symbols and progressively we will find the result for the original problem.
If we have a boolean expression of the type – X1 O X2 where X1 and X2 are boolean expressions and O is an operator, then we have,
If O==OR,
result=(number of ways in which X1 results in true)*(number of ways in which X2 results in true) + (number of ways in which X1 results in true)*(number of ways in which X2 results in false) + (number of ways in which X1 results in false)*(number of ways in which X2 results in true)
If O==AND,
result=(number of ways in which X1 results in true)*(number of ways in which X2 results in true)
If O==XOR,
result=(number of ways in which X1 results in false)*(number of ways in which X2 results in true) +(number of ways in which X1 results in true)*(number of ways in which X2 results in false)
Case-1:
Expression - True Or True And False Xor True Expected result= 4
Here is source code of the C++ Program to Solve Counting Boolean Parenthesization Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int c[100];
void catalan(int n)
{
//we have n pairs of parentheses
//we have to find the total number of strings that are possible with n pairs of parentheses that are correctly matched
//c[i]=total number of strings that are possible with n correctly matched pairs of parentheses
//we know that for 0 pairs, only one string possible (empty string)
//for a single node, there can be only 1 string ie, ()
//for 2 nodes, there can be just 2 strings ie, ()() and (())
//so, we initialize the array with these values
c[0]=1;
c[1]=1;
c[2]=2;
int i,j;
//now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value
for(i=3;i<=n;i++)
{
c[i]=0;
for(j=0;j<i;j++)
{
c[i]+=c[j] * c[(i-1)-j];
}
}
}
int booleanParen(string expression)
{
int n=(expression.length()+1)/2;
int i,j,k;
//index of symbol number i in the expression string is equal to i*2
int indexSymbol;
//index of operator following symbol number i in the expression string is equal to i*2+1
int indexOperator;
int left, right;
vector<vector<int> > dp(n,vector<int>(n,0));
//initialize
//for one symbol
for(i=0;i<n;i++)
{
indexSymbol=i*2;
if(expression[indexSymbol]=='T')
dp[i][i]=1;
}
//for 2 symbols
for(i=0;i<n-1;i++)
{
j=i+1;
indexOperator=2*i+1;
//and
if(expression[indexOperator]=='A')
{
dp[i][j]=dp[i][i]*dp[j][j];
}
//or
else if(expression[indexOperator]=='O')
{
if(expression[2*i]=='T' || expression[2*j]=='T')
dp[i][j]=1;
}
//xor
else
{
if( (expression[2*i]=='T' && expression[2*j]=='F') || (expression[2*i]=='F' && expression[2*j]=='T') )
dp[i][j]=1;
}
}
//length of number of symbols
for(int len=3;len<=n;len++)
{
for(i=0;i<=n-len;i++)
{
j=i+len-1;
//now divide the symbols i...j into two parts ie. i...k and k+1...j
for(k=i;k<j;k++)
{
indexOperator=2*k+1;
//and
if(expression[indexOperator]=='A')
{
//result=(number of true combinations on left side) * (number of true combinations on right side of operator)
dp[i][j]+=dp[i][k]*dp[k+1][j];
}
//or
else if(expression[indexOperator]=='O')
{
//result=(true on left)*(true on right)
// + (true on left)*(false on right)
// + (false on left)*(true on right)
left=c[k-i];
right=c[j-(k+1)];
dp[i][j]+=(dp[i][k]*dp[k+1][j]) + (dp[i][k]*(right-dp[k+1][j])) + ((left-dp[i][k])*dp[k+1][j]);
}
//xor
else
{
//result=(true on left)*(false on right)
// +(false on left)*(true on right)
left=c[k-i];
right=c[j-(k+1)];
dp[i][j]+=(dp[i][k]*(right-dp[k+1][j])) + ((left-dp[i][k])*dp[k+1][j]);
}
}
}
}
return dp[0][n-1];
}
int main()
{
int i,j,k;
string expression;
cout<<"Enter the boolean expression"<<endl;
cout<<"T for TRUE, F for FALSE, A for AND, O for or and X for XOR"<<endl;
cout<<"For Example- (TOTXFAT) is for (TRUE | TRUE ^ FALSE & TRUE) "<<endl;
getline(cin,expression);
catalan((expression.length()+1)/2);
bool invalid=false;
if(expression.length()==0 || expression.length()%2==0)
{
invalid=true;
cout<<"Invalid Expression";
}
else
{
for(i=0;i<expression.length();i++)
{
if(i%2==0)
{
//even position
//symbol
if(expression[i]=='A' || expression[i]=='O' || expression[i]=='X')
{
cout<<"Invalid Expression";
cout<<endl<<"Expression is not in the required format";
invalid=true;
break;
}
}
else
{
//odd position
//operator
if(expression[i]=='T' || expression[i]=='F')
{
cout<<"Invalid Expression";
cout<<endl<<"Expression is not in the required format";
invalid=true;
break;
}
}
}
}
if(!invalid)
{
int result=booleanParen(expression);
cout<<"The number of ways in which the expression can be parenthesized to give true is "<<endl<<result;
}
cout<<endl;
return 0;
}
In the main function, we ask the user to input the boolean expression in a proper format. Then, we will generate catalan numbers using the catalan function and store then in the array c. Then we will analyze the expression for validity. If the expression is invalid, it will be reported. For a valid expression, the expression will be passed to the function booleanParen as a parameter which will calculate the expected result and return it. The returned value will be displayed.
Case-1: $ g++ boolean_parenthesization.cpp $ ./a.out Enter the boolean expression T for TRUE, F for FALSE, A for AND, O for or and X for XOR For Example- (TOTXFAT) is for (TRUE | TRUE ^ FALSE & TRUE) TOFATXF The number of ways in which the expression can be parenthesized to give true is 5
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Check Data Structure Books
- Check Programming Books
- Practice Design & Analysis of Algorithms MCQ
- Apply for Computer Science Internship
- Check Computer Science Books