Boolean Parenthesization Problem

Given a boolean expression with following symbols.

Symbols
    'T' ---> true 
    'F' ---> false

And following operators filled between symbols

Operators
    &   ---> boolean AND
    |   ---> boolean OR
    ^   ---> boolean XOR

Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.

Let the input be in form of two arrays one contains the symbols (T and F) in order and other contains operators (&, | and ^}

Examples:

Input: symbol[]    = {T, F, T}
       operator[]  = {^, &}
Output: 2
The given expression is "T ^ F & T", it evaluates true
in two ways "((T ^ F) & T)" and "(T ^ (F & T))"

Input: symbol[]    = {T, F, F}
       operator[]  = {^, |}
Output: 2
The given expression is "T ^ F | F", it evaluates true
in two ways "( (T ^ F) | F )" and "( T ^ (F | F) )". 

Input: symbol[]    = {T, T, F, T}
       operator[]  = {|, &, ^}
Output: 4
The given expression is "T | T & F ^ T", it evaluates true
in 4 ways ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) 
and (T|((T&F)^T)). 

Solution:
Let T(i, j) represents the number of ways to parenthesize the symbols between i and j (both inclusive) such that the subexpression between i and j evaluates to true.

 

 

 

 

Let F(i, j) represents the number of ways to parenthesize the symbols between i and j (both inclusive) such that the subexpression between i and j evaluates to false.

 

 

 

 

[ad type=”banner”]

Base Cases:

T(i, i) = 1 if symbol[i] = 'T' 
T(i, i) = 0 if symbol[i] = 'F' 

F(i, i) = 1 if symbol[i] = 'F' 
F(i, i) = 0 if symbol[i] = 'T'

If we draw recursion tree of above recursive solution, we can observe that it many overlapping subproblems. Like other dynamic programming problems, it can be solved by filling a table in bottom up manner. Following is C++ implementation of dynamic programming solution.

[pastacode lang=”cpp” manual=”%23include%3Ciostream%3E%0A%23include%3Ccstring%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Returns%20count%20of%20all%20possible%20parenthesizations%20that%20lead%20to%0A%2F%2F%20result%20true%20for%20a%20boolean%20expression%20with%20symbols%20like%20true%0A%2F%2F%20and%20false%20and%20operators%20like%20%26%2C%20%7C%20and%20%5E%20filled%20between%20symbols%0Aint%20countParenth(char%20symb%5B%5D%2C%20char%20oper%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20F%5Bn%5D%5Bn%5D%2C%20T%5Bn%5D%5Bn%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Fill%20diaginal%20entries%20first%0A%20%20%20%20%2F%2F%20All%20diagonal%20entries%20in%20T%5Bi%5D%5Bi%5D%20are%201%20if%20symbol%5Bi%5D%0A%20%20%20%20%2F%2F%20is%20T%20(true).%20%20Similarly%2C%20all%20F%5Bi%5D%5Bi%5D%20entries%20are%201%20if%0A%20%20%20%20%2F%2F%20symbol%5Bi%5D%20is%20F%20(False)%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20F%5Bi%5D%5Bi%5D%20%3D%20(symb%5Bi%5D%20%3D%3D%20’F’)%3F%201%3A%200%3B%0A%20%20%20%20%20%20%20%20T%5Bi%5D%5Bi%5D%20%3D%20(symb%5Bi%5D%20%3D%3D%20’T’)%3F%201%3A%200%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Now%20fill%20T%5Bi%5D%5Bi%2B1%5D%2C%20T%5Bi%5D%5Bi%2B2%5D%2C%20T%5Bi%5D%5Bi%2B3%5D…%20in%20order%0A%20%20%20%20%2F%2F%20And%20F%5Bi%5D%5Bi%2B1%5D%2C%20F%5Bi%5D%5Bi%2B2%5D%2C%20F%5Bi%5D%5Bi%2B3%5D…%20in%20order%0A%20%20%20%20for%20(int%20gap%3D1%3B%20gap%3Cn%3B%20%2B%2Bgap)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%2C%20j%3Dgap%3B%20j%3Cn%3B%20%2B%2Bi%2C%20%2B%2Bj)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20T%5Bi%5D%5Bj%5D%20%3D%20F%5Bi%5D%5Bj%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20g%3D0%3B%20g%3Cgap%3B%20g%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Find%20place%20of%20parenthesization%20using%20current%20value%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20of%20gap%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20k%20%3D%20i%20%2B%20g%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Store%20Total%5Bi%5D%5Bk%5D%20and%20Total%5Bk%2B1%5D%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20tik%20%3D%20T%5Bi%5D%5Bk%5D%20%2B%20F%5Bi%5D%5Bk%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20tkj%20%3D%20T%5Bk%2B1%5D%5Bj%5D%20%2B%20F%5Bk%2B1%5D%5Bj%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Follow%20the%20recursive%20formulas%20according%20to%20the%20current%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20operator%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(oper%5Bk%5D%20%3D%3D%20’%26′)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20T%5Bi%5D%5Bj%5D%20%2B%3D%20T%5Bi%5D%5Bk%5D*T%5Bk%2B1%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20F%5Bi%5D%5Bj%5D%20%2B%3D%20(tik*tkj%20-%20T%5Bi%5D%5Bk%5D*T%5Bk%2B1%5D%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(oper%5Bk%5D%20%3D%3D%20’%7C’)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20F%5Bi%5D%5Bj%5D%20%2B%3D%20F%5Bi%5D%5Bk%5D*F%5Bk%2B1%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20T%5Bi%5D%5Bj%5D%20%2B%3D%20(tik*tkj%20-%20F%5Bi%5D%5Bk%5D*F%5Bk%2B1%5D%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(oper%5Bk%5D%20%3D%3D%20’%5E’)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20T%5Bi%5D%5Bj%5D%20%2B%3D%20F%5Bi%5D%5Bk%5D*T%5Bk%2B1%5D%5Bj%5D%20%2B%20T%5Bi%5D%5Bk%5D*F%5Bk%2B1%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20F%5Bi%5D%5Bj%5D%20%2B%3D%20T%5Bi%5D%5Bk%5D*T%5Bk%2B1%5D%5Bj%5D%20%2B%20F%5Bi%5D%5Bk%5D*F%5Bk%2B1%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20T%5B0%5D%5Bn-1%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20char%20symbols%5B%5D%20%3D%20%22TTFT%22%3B%0A%20%20%20%20char%20operators%5B%5D%20%3D%20%22%7C%26%5E%22%3B%0A%20%20%20%20int%20n%20%3D%20strlen(symbols)%3B%0A%20%0A%20%20%20%20%2F%2F%20There%20are%204%20ways%0A%20%20%20%20%2F%2F%20((T%7CT)%26(F%5ET))%2C%20(T%7C(T%26(F%5ET)))%2C%20(((T%7CT)%26F)%5ET)%20and%20(T%7C((T%26F)%5ET))%0A%20%20%20%20cout%20%3C%3C%20countParenth(symbols%2C%20operators%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++” highlight=”” provider=”manual”/]

Output :

4

Time Complexity: O(n³)
Auxiliary Space: O(n²)

[ad type=”banner”]