{"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
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/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
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n[ad type=”banner”]\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
 
 C++<\/span> <\/div> 
#include<iostream>#include<cstring>using namespace std; \/\/ Returns count of all possible parenthesizations that lead to\/\/ result true for a boolean expression with symbols like true\/\/ and false and operators like &, | and ^ filled between symbolsint countParenth(char symb[], char oper[], int n){    int F[n][n], T[n][n];     \/\/ Fill diaginal entries first    \/\/ All diagonal entries in T[i][i] are 1 if symbol[i]    \/\/ is T (true).  Similarly, all F[i][i] entries are 1 if    \/\/ symbol[i] is F (False)    for (int i = 0; i < n; i++)    {        F[i][i] = (symb[i] == 'F')? 1: 0;        T[i][i] = (symb[i] == 'T')? 1: 0;    }     \/\/ Now fill T[i][i+1], T[i][i+2], T[i][i+3]... in order    \/\/ And F[i][i+1], F[i][i+2], F[i][i+3]... in order    for (int gap=1; gap<n; ++gap)    {        for (int i=0, j=gap; j<n; ++i, ++j)        {            T[i][j] = F[i][j] = 0;            for (int g=0; g<gap; g++)            {                \/\/ Find place of parenthesization using current value                \/\/ of gap                int k = i + g;                 \/\/ Store Total[i][k] and Total[k+1][j]                int tik = T[i][k] + F[i][k];                int tkj = T[k+1][j] + F[k+1][j];                 \/\/ Follow the recursive formulas according to the current                \/\/ operator                if (oper[k] == '&')                {                    T[i][j] += T[i][k]*T[k+1][j];                    F[i][j] += (tik*tkj - T[i][k]*T[k+1][j]);                }                if (oper[k] == '|')                {                    F[i][j] += F[i][k]*F[k+1][j];                    T[i][j] += (tik*tkj - F[i][k]*F[k+1][j]);                }                if (oper[k] == '^')                {                    T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j];                    F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j];                }            }        }    }    return T[0][n-1];} \/\/ Driver program to test above functionint main(){    char symbols[] = "TTFT";    char operators[] = "|&^";    int n = strlen(symbols);     \/\/ There are 4 ways    \/\/ ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T))    cout << countParenth(symbols, operators, n);    return 0;}<\/code><\/pre> <\/div>\n
Output :<\/strong><\/p>\n
4<\/pre>\n
Time Complexity: O(n3<\/sup>)
\nAuxiliary Space: O(n2<\/sup>)<\/p>\n[ad type=”banner”]\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}]}}