Databases
StackOverflow2013
Postsdbo
POcounting boolean parenthesizations implementation
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POcounting boolean parenthesizations implementation
    text
    copied!<p>Given a boolean expression containing the symbols {true, false, and, or, xor}, count the number of ways to parenthesize the expression such that it evaluates to true.</p> <p>For example, there is only 1 way to parenthesize 'true and false xor true' such that it evaluates to true.</p> <p>Here is my algorithm</p> <pre><code>we can calculate the total number of parenthesization of a string Definition: N - the total number of True - the number of parenthesizations that evaluates to true False - the number of parenthesizations that evaluates to false True + False = N Left_True - the number of parenthesization in the left part that evaluates to True same to Left_False, Right_True, Right_False we iterate the input string from left to right and deal with each operator as follows: if it is "and", the number of parenthesization leads to true is Left_True * Right_True; if it is "xor", the number of parenthesization leads to true Left_True * Right_False + Left_False * Right_True if it is 'or', the number is N - Left_False * Right_False Here is my psuedocode n = number of operator within the String int[n][n] M; // save number of ways evaluate to true for l = 2 to n for i = 1 to n-l+1 do j = i+l-1 // here we have different string varying from 2 to n starting from i and ending at j for k = i to j-1 // (i,k-1) is left part // (k+1, j) is right part switch(k){ case 'and': // calculate, update array m case 'or': // same case 'xor': } we save all the solutions to subproblems and read them when we meet them again. thus save time. </code></pre> <p>Can we have a better solution? </p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload