# How to solve Boolean Parenthesization Problem in Python

In this tutorial, we will learn about an array 1/0 operand and another array operator.
The number of different methods (parentheses) used to group these operands is always correct.
Operators will always be one of these: & ;; |, ^ (And, or XOR). Its called a Boolean parenthesis problem.

For example 1:

Operation = [1,0,0]
Operator = [|, ^]

Then the above methods can have parentheses to get 1:
1 | (0 ^ 0)
(1 | 0) ^ 0 |

For example 2:

Operation = [1, 0, 1]
Operator = [|, ^, and]

Ways to generate 1:
(1 | (0 ^ 0)) and 1
((1 | 0) ^ 0) & 1

Solution:
So, we say that T (i, j) represents the number of ways of evaluating 1 and i.
0 (i, j) represents the number of ways to evaluate from 0 between i and j.

then T(i,j) =

summation() for all k between i and j

if operator[k] is &,   T(i,k) * T(k+1,j)

if operator[k] is |,   T(i,k) * T(k+1,j)  +   F(i,k) * T(k+1,j)  +   T(i,k) * F(k+1,j)

if operator[k] is ^,   F(i,k) * T(k+1,j)  +   T(i,k) * F(k+1,j)

and F(i,j) =

summation() for all k between i and j

if operator[k] is &,   F(i,k) * F(k+1,j)  +   F(i,k) * T(k+1,j)   +   T(i,k) * F(k+1,j)

if operator[k] is |,   F(i,k) * F(k+1,j)

if operator[k] is ^,   T(i,k) * T(k+1,j)  +   F(i,k) * F(k+1,j)
def countParenth(symb, oper, n):
F = [[0 for i in range(n + 1)]
for i in range(n + 1)]
T = [[0 for i in range(n + 1)]
for i in range(n + 1)]

for i in range(n):
if symb[i] == 'F':
F[i][i] = 1
else:
F[i][i] = 0

if symb[i] == 'T':
T[i][i] = 1
else:
T[i][i] = 0

for gap in range(1, n):
i = 0
for j in range(gap, n):
T[i][j] = F[i][j] = 0
for g in range(gap):

k = i + g

tik = T[i][k] + F[i][k];
tkj = T[k + 1][j] + F[k + 1][j];

if oper[k] == '&':
T[i][j] += T[i][k] * T[k + 1][j]
F[i][j] += (tik * tkj - T[i][k] *
T[k + 1][j])
if oper[k] == '|':
F[i][j] += F[i][k] * F[k + 1][j]
T[i][j] += (tik * tkj - F[i][k] *
F[k + 1][j])
if oper[k]=='^':
T[i][j] += (F[i][k] * T[k + 1][j] +
T[i][k] * F[k + 1][j])
F[i][j] += (T[i][k] * T[k + 1][j] +
F[i][k] * F[k + 1][j])
i += 1
return T[0][n - 1]

symbols = "TTFT"
operators = "|&^"
n = len(symbols)

print(countParenth(symbols, operators, n))

Output:

4

Time Complexity:

Complexity of  dynamic programming approach to find ways to parenthesize a Boolean expression to evaluate it to True is O(n^3). and space complexity is O(n^2).