[CC150v5] 9.11 Parenthesize the Expression - Shuatiblog.com

[CC150v5] 9.11 Parenthesize the Expression - Shuatiblog.com

[CC150v5] 9.11 Parenthesize the Expression

| Comments

Question

Given a boolean expression consisting of the symbols 0, 1, '&', '|', and '^', and a desired boolean result value 'result'.

Now implement a function to count the number of ways of parenthesizing the expression such that it evaluates to 'result'.

Solution

This is a difficult question.

Each parenthesized expression must have an outermost pair of parentheses.

That is, we can iterate through the expression, treating each operator as the first operator to be parenthesized.

Nice idea suggested in the book! So for each operator, we consider is as first operator (to evaluate), and then we shall if the total possible count.

(Note that while coding, we DO NOT WRITE {if-else if-else…} but instead use {if… if… if…} in order to get the total count. )

DP is more time-efficient.

Like CC150v5 Q9.10, the code given in the book is very hard to read. I have my own code posted below.

Read full article from [CC150v5] 9.11 Parenthesize the Expression - Shuatiblog.com