# 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).

## Leave a Reply

You must be logged in to post a comment.