We are given a Boolean expression as a sequence of n logic values

$($which can be T $($true$)$ or F $($false$))$ alternating with a sequence of n$1$

Boolean operators $($which can be $($AND$)$ or $($OR$)).$ We would like

to count the number of possible parenthesizations of the expression

such that it will evaluate to T $($true$).$ For example, if the expression is

T$$F$$F$$F$,$ there are two ways to parenthesize the expression to

Page $2$ of $2$

evaluate to true, since both $($T$(($F$$F$)$F$))$ and $($T$($F$($F$$F$)))$ evaluate

to T$,$ but all other parenthesizations evaluate to F$.$ Describe a dynamic

programming algorithm that will accomplish this task efficiently. You

do not need to determine the parenthesizations that will evaluate to

true, you just need to count the number of such parenthesizations.