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