Boolean Parenthesization Problem using Dynamic Programming

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.

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)

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.

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

```
 
```
```
#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;
```
```
}
```

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.

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.

« Prev - Dice Throw Problem – Dynamic Programming Solutions

» Next - Subset Sum Problem using Dynamic Programming

Related Posts:

Check Data Structure Books
Check Programming Books
Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Check Computer Science Books

Recommended Articles: