{"id":27185,"date":"2018-01-03T22:14:29","date_gmt":"2018-01-03T16:44:29","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27185"},"modified":"2018-01-03T22:14:29","modified_gmt":"2018-01-03T16:44:29","slug":"boolean-parenthesization-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/boolean-parenthesization-problem\/","title":{"rendered":"Boolean Parenthesization Problem"},"content":{"rendered":"

Given a boolean expression with following symbols.<\/span><\/p>\n

Symbols<\/strong>\r\n    'T' ---> true \r\n    'F' ---> false<\/pre>\n
And following operators filled between symbols<\/p>\n
Operators<\/strong>\r\n    &   ---> boolean AND\r\n    |   ---> boolean OR\r\n    ^   ---> boolean XOR<\/pre>\n
Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.<\/p>\n
Let the input be in form of two arrays one contains the symbols (T and F) in order and other contains operators (&, | and ^}<\/p>\n
Examples:<\/strong><\/p>\n
Input: symbol[]    = {T, F, T}\r\n       operator[]  = {^, &}\r\nOutput: 2\r\nThe given expression is \"T ^ F & T\", it evaluates true\r\nin two ways \"((T ^ F) & T)\" and \"(T ^ (F & T))\"\r\n\r\nInput: symbol[]    = {T, F, F}\r\n       operator[]  = {^, |}\r\nOutput: 2\r\nThe given expression is \"T ^ F | F\", it evaluates true\r\nin two ways \"( (T ^ F) | F )\" and \"( T ^ (F | F) )\". \r\n\r\nInput: symbol[]    = {T, T, F, T}\r\n       operator[]  = {|, &, ^}\r\nOutput: 4\r\nThe given expression is \"T | T & F ^ T\", it evaluates true\r\nin 4 ways ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) \r\nand (T|((T&F)^T)). \r\n<\/pre>\n
Solution:<\/strong>
\nLet T(i, j)<\/strong><\/u> represents the number of ways to parenthesize the symbols between i and j (both inclusive) such that the subexpression between i and j evaluates to true.<\/p>\n
\"True<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n
Let F(i, j)<\/strong><\/u> represents the number of ways to parenthesize the symbols between i and j (both inclusive) such that the subexpression between i and j evaluates to false.<\/p>\n
\"False<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n[ad type=\u201dbanner\u201d]\n
Base Cases:<\/p>\n
T(i, i) = 1 if symbol[i] = 'T' \r\nT(i, i) = 0 if symbol[i] = 'F' \r\n\r\nF(i, i) = 1 if symbol[i] = 'F' \r\nF(i, i) = 0 if symbol[i] = 'T'<\/pre>\n
If we draw recursion tree of above recursive solution, we can observe that it many overlapping subproblems. Like other dynamic programming problems, it can be solved by filling a table in bottom up manner. Following is C++ implementation of dynamic programming solution.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%3Ciostream%3E%0A%23include%3Ccstring%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Returns%20count%20of%20all%20possible%20parenthesizations%20that%20lead%20to%0A%2F%2F%20result%20true%20for%20a%20boolean%20expression%20with%20symbols%20like%20true%0A%2F%2F%20and%20false%20and%20operators%20like%20%26%2C%20%7C%20and%20%5E%20filled%20between%20symbols%0Aint%20countParenth(char%20symb%5B%5D%2C%20char%20oper%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20F%5Bn%5D%5Bn%5D%2C%20T%5Bn%5D%5Bn%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Fill%20diaginal%20entries%20first%0A%20%20%20%20%2F%2F%20All%20diagonal%20entries%20in%20T%5Bi%5D%5Bi%5D%20are%201%20if%20symbol%5Bi%5D%0A%20%20%20%20%2F%2F%20is%20T%20(true).%20%20Similarly%2C%20all%20F%5Bi%5D%5Bi%5D%20entries%20are%201%20if%0A%20%20%20%20%2F%2F%20symbol%5Bi%5D%20is%20F%20(False)%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20F%5Bi%5D%5Bi%5D%20%3D%20(symb%5Bi%5D%20%3D%3D%20\u2019F\u2019)%3F%201%3A%200%3B%0A%20%20%20%20%20%20%20%20T%5Bi%5D%5Bi%5D%20%3D%20(symb%5Bi%5D%20%3D%3D%20\u2019T\u2019)%3F%201%3A%200%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Now%20fill%20T%5Bi%5D%5Bi%2B1%5D%2C%20T%5Bi%5D%5Bi%2B2%5D%2C%20T%5Bi%5D%5Bi%2B3%5D\u2026%20in%20order%0A%20%20%20%20%2F%2F%20And%20F%5Bi%5D%5Bi%2B1%5D%2C%20F%5Bi%5D%5Bi%2B2%5D%2C%20F%5Bi%5D%5Bi%2B3%5D\u2026%20in%20order%0A%20%20%20%20for%20(int%20gap%3D1%3B%20gap%3Cn%3B%20%2B%2Bgap)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%2C%20j%3Dgap%3B%20j%3Cn%3B%20%2B%2Bi%2C%20%2B%2Bj)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20T%5Bi%5D%5Bj%5D%20%3D%20F%5Bi%5D%5Bj%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20g%3D0%3B%20g%3Cgap%3B%20g%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Find%20place%20of%20parenthesization%20using%20current%20value%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20of%20gap%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20k%20%3D%20i%20%2B%20g%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Store%20Total%5Bi%5D%5Bk%5D%20and%20Total%5Bk%2B1%5D%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20tik%20%3D%20T%5Bi%5D%5Bk%5D%20%2B%20F%5Bi%5D%5Bk%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20tkj%20%3D%20T%5Bk%2B1%5D%5Bj%5D%20%2B%20F%5Bk%2B1%5D%5Bj%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Follow%20the%20recursive%20formulas%20according%20to%20the%20current%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20operator%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(oper%5Bk%5D%20%3D%3D%20\u2019%26\u2032)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20T%5Bi%5D%5Bj%5D%20%2B%3D%20T%5Bi%5D%5Bk%5D*T%5Bk%2B1%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20F%5Bi%5D%5Bj%5D%20%2B%3D%20(tik*tkj%20-%20T%5Bi%5D%5Bk%5D*T%5Bk%2B1%5D%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(oper%5Bk%5D%20%3D%3D%20\u2019%7C\u2019)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20F%5Bi%5D%5Bj%5D%20%2B%3D%20F%5Bi%5D%5Bk%5D*F%5Bk%2B1%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20T%5Bi%5D%5Bj%5D%20%2B%3D%20(tik*tkj%20-%20F%5Bi%5D%5Bk%5D*F%5Bk%2B1%5D%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(oper%5Bk%5D%20%3D%3D%20\u2019%5E\u2019)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20T%5Bi%5D%5Bj%5D%20%2B%3D%20F%5Bi%5D%5Bk%5D*T%5Bk%2B1%5D%5Bj%5D%20%2B%20T%5Bi%5D%5Bk%5D*F%5Bk%2B1%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20F%5Bi%5D%5Bj%5D%20%2B%3D%20T%5Bi%5D%5Bk%5D*T%5Bk%2B1%5D%5Bj%5D%20%2B%20F%5Bi%5D%5Bk%5D*F%5Bk%2B1%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20T%5B0%5D%5Bn-1%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20char%20symbols%5B%5D%20%3D%20%22TTFT%22%3B%0A%20%20%20%20char%20operators%5B%5D%20%3D%20%22%7C%26%5E%22%3B%0A%20%20%20%20int%20n%20%3D%20strlen(symbols)%3B%0A%20%0A%20%20%20%20%2F%2F%20There%20are%204%20ways%0A%20%20%20%20%2F%2F%20((T%7CT)%26(F%5ET))%2C%20(T%7C(T%26(F%5ET)))%2C%20(((T%7CT)%26F)%5ET)%20and%20(T%7C((T%26F)%5ET))%0A%20%20%20%20cout%20%3C%3C%20countParenth(symbols%2C%20operators%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output :<\/strong><\/p>\n
4<\/pre>\n
Time Complexity: O(n3<\/sup>)
\nAuxiliary Space: O(n2<\/sup>)<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Boolean Parenthesization Problem – Dynamic Programming Count the number of ways we can parenthesize the expression so that the value of expression<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83847,70145],"tags":[81034,81029,81035,81038,81030,81032,81031,72848,72840,72846,72985,72844,81041],"class_list":["post-27185","post","type-post","status-publish","format-standard","hentry","category-boolean-parenthesization","category-dynamic-programming","tag-2-dimensional-algorithms-practice-problems","tag-boolean-parenthesisation-problem-dynamic-programming","tag-boolean-parenthesization-in-c-code","tag-boolean-parenthesization-problem-java","tag-counting-boolean-parenthesization-problem","tag-counting-boolean-parenthesizations","tag-counting-boolean-parenthesizations-implementation","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-java","tag-dynamic-programming-software","tag-evaluate-expression-to-in-c-program"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27185","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27185"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27185\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}