I recently came across this question: "You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there are two ways to parenthesize 'true and false xor true' such that it evaluates to true."
I knew it is a dynamic programming problem so i tried to come up with a solution on my own which is as follows. Suppose we have a expression as A.B.C…..D where '.' represents any of the operations and, or, xor and the capital letters represent true or false. Lets say the number of ways for this expression of size K to produce a true is N. when a new boolean value E is added to this expression there are 2 ways to parenthesize this new expression 1. ((A.B.C…..D).E) ie. with all possible parenthesizations of A.B.C…..D we add E at the end.
2. (A.B.C.(D.E)) ie. evaluate D.E first and then find the number of ways this expression of size K can produce true.
suppose T[K] is the number of ways the expression with size K produces true then T[k]=val1+val2+val3 where val1,val2,val3 are calculated as follows.
1)when E is grouped with D.
i)It does not change the value of D
ii)it inverses the value of D
in the first case val1=T[K]=N.( As this reduces to the initial A.B.C….D expression ).
In the second case re-evaluate dp[K] with value of D reversed and that is val1.
2)when E is grouped with the whole expression.
//val2 contains the number of 'true' E will produce with expressions which gave 'true' among all parenthesized instances of A.B.C…….D
i) if true.E = true then val2 = N
ii) if true.E = false then val2 = 0
//val3 contains the number of 'true' E will produce with expressions which gave 'false' among all parenthesized instances of A.B.C…….D
iii) if false.E=true then val3=( 2^(K-2) – N ) = M ie. number of ways the expression with size K produces a false [ 2^(K-2) is the number of ways to parenthesize an expression of size K ].
iv) if false.E=false then val3 = 0
This is the basic idea i had in mind but when i checked for its solution http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf the approach there was completely different. Can someone tell me what am I doing wrong and how can i get better at solving DP so that I can come up with solutions like the one given above myself.
Thanks in advance.
Best Answer
The answer, as with many things, is:
Practice, practice, practice.
By the way, I believe that in your solution you got into a dead-end by making a trivial mistake really early on: "There are 2 ways to parenthesize this new expression" -- aren't there more than 2? How about
(A.B.(C.D.E)), for example?