I'm trying to figure how to flatten a parenthesized boolean expression into a set of ordered expressions that are logically the same.

Question

So let's say I've got an expression like this:

((((e1) or (e2)) and (e3 or (e5 and e6)) and (e7)) or (e8))

I need to end up with a list of expressions (e1, e2, e3 etc) followed by and/or operators so that evaluating the list from left to right yields the same logical boolean answer.

ie e1 or e2 and e5 and e6 or e3 and e7 or e8. But that's not the right answer, but that's the kind of thing I need to end up with.

I know a recursive descent parser will evaluate the expression, but that's not what I need, I need to end up with a list of expressions that can be evaluated later left to right.

I was thinking put it in a binary tree and then navigate the tree postfix or something like that, but that doesn't seem right to be.

I used to be smart enough to figure out things like this, but now I have a baby and have lost all of my higher cognitive abilities. Help?

Answer 1

First off, what you are looking to do is convert infix notation to postfix notation.

You are on the right track with your thoughts about a parser, for indeed you need to parse (but not evaluate) the original expression, and then print it out in postfix notation.

Answer 2

My dad with his near infinite intelligence (despite having 2 kids) points out a rather simple solution: demorgan's law says you can rewrite any expression to use only ANDs or ORs with various uses of NOT. So simply convert all of the AND expressions to their OR equivalent, remove the parenthesis, and evaluate left to right. Very workable idea, except that in my case the NOT operation is terribly expensive.