0

I am trying to solve the boolean expression optimization problem for a simple rule engine.

Here is what I am trying to do, lets say if I have following 5 conditions (where a,b,c,d,e,f are complex boolean expressions)

if (a AND b AND c AND d AND e AND f) then do-1 
if (a AND b AND c AND d AND e) then do-2 
if (a AND b AND c AND d) then do-3
if (a AND b AND c) then do-4
if (a AND b) then do-5

In case when I execute these conditions in a linear order I will 

- evaluate "a" for 5 times
- evaluate "b" for 5 times
- evaluate "c" for 4 times
- evaluate "d" for 3 times
- evaluate "e" for 2 times
- evaluate "f" for 1 time

I would like to make a expression execution tree from this so that each expression (a,b,c,d,e,f) is evaluated minimum number of times. The perfect solution will be that each expression is evaluated only once. I think this can be achieved with a tree creation where all these conditions are part of a tree.

The tree may look like this 

if(a AND b) then do-5  {
    if(c) then do-4 {
        if(d) then do-3 {
            if(e) then do-2 {
                if(f) then do-1 
            }
        }
    }       
}

My questions is - How can I make this tree from the set of boolean expressions listed above?

Related Questions:

Algorithm for evaluating nested logical expression

Converting an expression to conjunctive normal form with a twist

Is it useful in C# to apply DeMorgan's theorem to manually optimize boolean expressions in conditional statements (e.g. if conditions)

Community
  • 1
  • 1
software.wikipedia
  • 709
  • 7
  • 17
  • What is the question? – tmr232 Dec 16 '14 at 13:26
  • @tmr232 - thanks for your response. Sorry I am in different timezone so late response. I have updated the questions. – software.wikipedia Dec 17 '14 at 17:22
  • If your five `if` statements above are source code (as opposed to coming out of a database, or something), it seems you can just do `bool atemp = a; bool btemp = b;`, and so on, and then just refer to those temps in the `if` statements. – 500 - Internal Server Error Dec 17 '14 at 18:21
  • This is more of a switch-case than a tree. I assume you have a list of all the booleans. If so, I would use `list_of_bools.index(False)` to get the correct case, then use a function table to jump to the correct code. – tmr232 Dec 17 '14 at 22:46
  • Thanks for your response. Sorry, it seems I am not able to describe my problem clearly. Let me think of a better way to describe. – software.wikipedia Dec 20 '14 at 03:23

1 Answers1

0

You could approach it this way:

var booleans = [a, b, c, d, e, f];
var i = 0;
while(booleans[i]) i++;

switch(i) {
    case 0:
        // do something
        break;
    case 1:
        // do something
        break;
    ...
}

I'm pretty sure there is a way to merge the while loop with the switch operator to get something even more optimized from this.

M. Paviza
  • 146
  • 1
  • 1
  • 8