counting boolean parenthesizations implementation

Question

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:


if 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?

Answer 1

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