**Counting Boolean Parenthesizations:**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 2 ways to parenthesize 'true and false xor true' such that it evaluates to true.

*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)

Auxiliary Space: O(n

^{2})

## No comments:

## Post a Comment