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