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 2 ways to parenthesize True AND False XOR True such that it evaluates to True.
Sub-problem definition
Let T[i, j] be the number of ways of parenthesizing the string S[i : j] such that the expression between indices i and j evaluates to True, and F[i, j] be the number of ways of parenthesizing the string S[i : j] such that the expression between indices i and j evaluates to False. Here indices i and j are inclusive.
Recursive formulation
Then, given that Tot[i, j]= T[i, j]+F[i, j], we see that T[i, j] and F[i, j] can be expressed by the following recursive formulations,
We have the following base cases, for all i between 1 and n,
The final answer is T[1,n] (the total number of ways of obtaining a final value of True given that the entire string S[1 : n] is used. Here, we are making a guess over the positions of the outermost parentheses in the expression sub-stringed between i and j.