counting boolean parenthesizations implementation

Given a boolean expression containing the symbols {true, false, and, or, xor}, count the number of ways to parenthesize the expression such that it evaluates to true.

For example, there is only 1 way to parenthesize 'true and false xor true' such that it evaluates to true.

Here is my algorithm

we can calculate the total number of parenthesization of a string
Definition:  
N - the total number of 
True -  the number of parenthesizations that evaluates to true
False - the number of parenthesizations that evaluates to false
True + False = N 
Left_True - the number of parenthesization in the left part that evaluates to True
same to Left_False, Right_True, Right_False

we iterate the input string from left to right and deal with each operator as follows:


i开发者_JS百科f it is "and", the number of parenthesization leads to true is
    Left_True * Right_True;

if it is "xor", the number of parenthesization leads to true
    Left_True * Right_False + Left_False * Right_True

if it is 'or', the number is
    N - Left_False * Right_False 

Here is my psuedocode 

n = number of operator within the String 

int[n][n] M; // save number of ways evaluate to true

for l = 2 to n
for i = 1 to n-l+1
  do j = i+l-1  
  // here we have different string varying from 2 to n starting from i and ending at j
  for k = i to j-1
  // (i,k-1) is left part
  // (k+1, j) is right part
  switch(k){
    case 'and':  // calculate, update array m
    case 'or':  // same
    case 'xor':
  }

  we save all the solutions to subproblems and read them when we meet them again. thus save time.

Can we have a better solution?

Your pseudocode gives an algorithm in O(2^n). I think you can have something in O(n^3).

First of all, let's see the complexity of your algorithm. Let's say that the number of operations needed to check the parenthesization is T(n). If I understood well, your algorithm consists of :

• Cut the expression in two (n-1 possibilities)

• Check if the left and the right part have appropriate parenthesization.

So T(n) = checking if you cut at the first place + checking if you cut at the second place + ... + checking if you cut at the last place

T(n) = T(1)+T(n-1) + T(2)+T(n-2) + ... + T(n-1)+T(1) + n

A bit of computation will tell you that T(n) = 2^n*T(1) + O(n^2) = O(2^n)

My idea is that what you only need is to check for parenthesization are the "subwords". The "subword_i_j" consists of all the litterals between position i and position j. Of course i<j so you have N*(N-1)/2 subwords. Let's say that L[i][j] is the number of valid parenthesizations of the subword_i_j. For the sake of convenience, I'll forget the other values M[i][j] that states the number of parenthesization that leads to false, but don't forget that it's here!

You want to compute all the possible subwords starting from the smallest ones (size 1) to the biggest one (size N).

You begin by computing L[i][i] for all i. There are N such values. It's easy, if the i-th litteral is True then L[i][i]=1 else L[i][i]=0. Now, you know the number of parenthesization for all subwords of size 1.

Lets say that you know the parenthesization for all subwords of size S.

Then compute L[i][i+S] for i between 1 and N-S. These are subwords of size S+1. It consists of splitting the subword in all possible ways (S ways), and checking if the left part(which is a subword of size S1<=S) and the right part(which is of size S2<=S) and the operator inbetween (or, xor, and) are compatible. There are S*(N-S) such values.

Finally, you'll end up with L[1][N] which will tell you if there is a valid parenthesization.

The cost is :

checking subwords of size 1 + checking subwords of size 2 + ... + checking subwords of size N

= N + N-1 + 2*(N-2) + 2*(N-2) + .. + (N-1)*(1)

= O(N^3)

The reason the complexity is better is that in your pseudocode, you check multiple times the same subwords without storing the result in memory.

Edit : Arglllll, I overlooked the sentence we save all the solutions to subproblems and read them when we meet them again. thus save time.. Well, seems that if you do, you also have an algorithm in worst-case O(N^3). Don't think you can do much better than that...

This problem can be solved by Dynamic-Algorithm and it is similar to Matrix chain multiplication problem, the detail answer is follow:

1、Let the operation consist of operand a_i and operator b_j (1<=i<=n, 1<=j<=n-1 n is the size of operand), substitute true for 1, substitute false for 0

2、Let DPone[i][j] be the number of ways to parenthesize in {a_i b_i a_i+1 ... b_j-1 b_j} such that the result is 1, Let DPzero[i][j] be the number of ways to parenthesize in {a_i b_i a_i+1 ... b_j-1 b_j} such that the result is 0

3、Build function oper(i,j,k), the return value is the number of ways such that operation's result is 1 when b_k is the last used operator in {a_i b_i a_i+1 ... b_j-1 b_j}, the direct operation method is based on b_k. For example, b_i is and, so the return value is DPone[i][k]*DPone[k+1][j].

4、Now the DP equation is follow:

DPone[i][j] = max{ sum ( oper(i,j,k) ) i<=k<=j-1 }

so we just need to determine DPone[1][n]. The complexity is O(n^3)

Intention:

1、We should determine DPzero[i][j] after determine DPone[i][j], but it's simple, DPzero[i][j]=total_Parenthesize_Ways[i][j]-DPone[i][j]

2、the order to find DPone is [1][1],[2][2],...[n][n],[1][2],[2][3],...[n-1][n],[1][3],[2][4]......[2][n],[1][n], of course, [1][1]~[n][n] should be initialized by ourselves.

Here is the code for counting parenthesizations for an array of booleans and operators.

Time complexity O(N^3) and space complexity O(N^2)

public static int CountingBooleanParenthesizations(bool[] boolValues, string[] operators)
{
    int[,] trueTable = new int[boolValues.Length, boolValues.Length];
    int[,] falseTable = new int[boolValues.Length, boolValues.Length];
    for (int j = 0; j < boolValues.Length; j++)
    {
        for (int i = j; i >= 0; i--)
        {
            if (i == j)
            {
                trueTable[i, j] = boolValues[i] ? 1 : 0;
                falseTable[i, j] = boolValues[i] ? 0 : 1;
            }
            else
            {
                int trueSum = 0;
                int falseSum = 0;
                for (int k = i; k < j; k++)
                {
                    int total1 = trueTable[i, k] + falseTable[i, k];
                    int total2 = trueTable[k + 1, j] + falseTable[k + 1, j];
                    switch (operators[k])
                    {
                        case "or":
                            {
                                int or = falseTable[i, k] * falseTable[k + 1, j];
                                falseSum += or;
                                or = total1 * total2 - or;
                                trueSum += or;
                            }
                            break;
                        case "and":
                            {
                                int and = trueTable[i, k] * trueTable[k + 1, j];
                                trueSum += and;
                                and = total1 * total2 - and;
                                falseSum += and;
                            }
                            break;
                        case "xor":
                            {
                                int xor = trueTable[i, k] * falseTable[k + 1, j] + falseTable[i, k] * trueTable[k + 1, j];
                                trueSum += xor;
                                xor = total1 * total2 - xor;
                                falseSum += xor;
                            }
                            break;
                    }
                }
                trueTable[i, j] = trueSum;
                falseTable[i, j] = falseSum;
            }
        }
    }
     return trueTable[0, boolValues.Length - 1];
}