Counting Boolean Parenthesization Problem – Dynamic Programming Solutions

«
»

This is a C++ Program that Solves Counting Boolean Parenthesization Problem using Dynamic Programming technique.

Problem Description

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.

Problem Solution

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.

advertisement

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)

advertisement
Expected Input and Output

Case-1:

Expression - True Or True And False Xor True
Expected result= 4
Program/Source Code

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.

  1.  
  2. #include<iostream>
  3. #include<vector>
  4. #include<string>
  5. using namespace std;
  6.  
  7. int c[100];
  8.  
  9. void catalan(int n)
  10. {
  11.     //we have n pairs of parentheses
  12.     //we have to find the total number of strings that are possible with n pairs of parentheses that are correctly matched
  13.  
  14.     //c[i]=total number of strings that are possible with n correctly matched pairs of parentheses    
  15.  
  16.     //we know that for 0 pairs, only one string possible (empty string)
  17.     //for a single node, there can be only 1 string ie, ()
  18.     //for 2 nodes, there can be just 2 strings ie, ()() and (()) 
  19.     //so, we initialize the array with these values
  20.     c[0]=1;
  21.     c[1]=1;
  22.     c[2]=2;
  23.  
  24.     int i,j;
  25.  
  26.     //now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value
  27.     for(i=3;i<=n;i++)
  28.     {
  29.         c[i]=0;
  30.  
  31.         for(j=0;j<i;j++)
  32.         {
  33.             c[i]+=c[j] * c[(i-1)-j];
  34.         }
  35.     }
  36.  
  37. }
  38.  
  39. int booleanParen(string expression)
  40. {
  41.     int n=(expression.length()+1)/2;
  42.     int i,j,k;
  43.  
  44.  
  45.     //index of symbol number i in the expression string is equal to i*2
  46.     int indexSymbol;
  47.  
  48.     //index of operator following symbol number i in the expression string is equal to i*2+1
  49.     int indexOperator;
  50.  
  51.     int left, right;
  52.  
  53.     vector<vector<int> > dp(n,vector<int>(n,0));
  54.  
  55.     //initialize
  56.     //for one symbol
  57.     for(i=0;i<n;i++)
  58.     {
  59.         indexSymbol=i*2;
  60.  
  61.         if(expression[indexSymbol]=='T')
  62.             dp[i][i]=1;
  63.     }
  64.  
  65.     //for 2 symbols
  66.     for(i=0;i<n-1;i++)
  67.     {
  68.         j=i+1;
  69.  
  70.         indexOperator=2*i+1;
  71.  
  72.         //and 
  73.         if(expression[indexOperator]=='A')
  74.         {
  75.             dp[i][j]=dp[i][i]*dp[j][j];
  76.         }
  77.  
  78.         //or
  79.         else if(expression[indexOperator]=='O')
  80.         {
  81.             if(expression[2*i]=='T' || expression[2*j]=='T')
  82.                 dp[i][j]=1;
  83.         }
  84.  
  85.         //xor
  86.         else
  87.         {
  88.             if( (expression[2*i]=='T' && expression[2*j]=='F') || (expression[2*i]=='F' && expression[2*j]=='T') )
  89.                 dp[i][j]=1;
  90.  
  91.         }
  92.     }
  93.  
  94.     //length of number of symbols 
  95.     for(int len=3;len<=n;len++)
  96.     {
  97.         for(i=0;i<=n-len;i++)
  98.         {
  99.             j=i+len-1;
  100.  
  101.             //now divide the symbols i...j into two parts ie. i...k and k+1...j
  102.             for(k=i;k<j;k++)
  103.             {
  104.  
  105.                 indexOperator=2*k+1;
  106.  
  107.                 //and
  108.                 if(expression[indexOperator]=='A')
  109.                 {
  110.                     //result=(number of true combinations on left side) * (number of true combinations on right side of operator)
  111.                     dp[i][j]+=dp[i][k]*dp[k+1][j];
  112.                 }
  113.  
  114.                 //or
  115.                 else if(expression[indexOperator]=='O')
  116.                 {
  117.                     //result=(true on left)*(true on right)
  118.                     //     + (true on left)*(false on right)
  119.                     //     + (false on left)*(true on right)
  120.  
  121.                     left=c[k-i];
  122.                     right=c[j-(k+1)];
  123.  
  124.                     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]);
  125.  
  126.                 }
  127.  
  128.                 //xor
  129.                 else
  130.                 {
  131.                     //result=(true on left)*(false on right)
  132.                     //      +(false on left)*(true on right)
  133.                     left=c[k-i];
  134.                     right=c[j-(k+1)];
  135.  
  136.                     dp[i][j]+=(dp[i][k]*(right-dp[k+1][j])) + ((left-dp[i][k])*dp[k+1][j]);
  137.  
  138.  
  139.                 }
  140.  
  141.  
  142.             }
  143.         }
  144.     }
  145.  
  146.  
  147.     return dp[0][n-1];
  148. }
  149.  
  150. int main()
  151. {
  152.     int i,j,k;
  153.     string expression;
  154.  
  155.     cout<<"Enter the boolean expression"<<endl;
  156.     cout<<"T for TRUE, F for FALSE, A for AND, O for or and X for XOR"<<endl;
  157.     cout<<"For Example- (TOTXFAT) is for (TRUE | TRUE ^ FALSE & TRUE) "<<endl;
  158.     getline(cin,expression);
  159.  
  160.     catalan((expression.length()+1)/2);
  161.  
  162.     bool invalid=false;
  163.  
  164.     if(expression.length()==0 || expression.length()%2==0)
  165.     {
  166.         invalid=true;
  167.         cout<<"Invalid Expression";
  168.     }
  169.  
  170.     else 
  171.     {
  172.         for(i=0;i<expression.length();i++)
  173.         {
  174.             if(i%2==0)
  175.             {
  176.                 //even position
  177.                 //symbol
  178.                 if(expression[i]=='A' || expression[i]=='O' || expression[i]=='X')
  179.                 {
  180.                     cout<<"Invalid Expression";
  181.                     cout<<endl<<"Expression is not in the required format";
  182.                     invalid=true;
  183.                     break;
  184.                 }
  185.             }
  186.  
  187.             else
  188.             {
  189.                 //odd position
  190.                 //operator
  191.                 if(expression[i]=='T' || expression[i]=='F')
  192.                 {
  193.                     cout<<"Invalid Expression";
  194.                     cout<<endl<<"Expression is not in the required format";
  195.                     invalid=true;
  196.                     break;
  197.                 }
  198.             }
  199.  
  200.         }
  201.     }
  202.  
  203.     if(!invalid)
  204.     {
  205.         int result=booleanParen(expression);
  206.  
  207.         cout<<"The number of ways in which the expression can be parenthesized to give true is "<<endl<<result;
  208.  
  209.     }
  210.  
  211.     cout<<endl;
  212.     return 0;
  213. }
Program Explanation

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.

advertisement
Runtime Test Cases
 
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.

advertisement
advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn