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.