Search code examples
infix-notationreductionprefix-operator

Algorithm to remove redundant parentheses from a boolean expression

I have a boolean expression in prefix notation. Lets say it is or and A B or or C D E. When I convert it to infix notation I end up with ((A and B) or ((C or D) or E)). I want to reduce it to (A and B) or C or D or E. Should I reduce infix notation or is it actually easier to get reduced equation from prefix notation. What algorithms should I use?

Solution

  • Paranthesis can be removed in expression X % (X1 ? X2 ? .. ? Xn) % X(n+1) where Xi is a parenthesized expression or boolean value "?" and "%" are operators if and only if each "?" operator has precedence higher or equal to "%" operator.

    For infix notation you would find innermost expression, check if parenthesis can be removed, save result, process parent expresion and continue until all parenthesis checks are done.

    This turns into a mapping problem. Postfix notation makes parenthesis elimination easy. Translation between prefix, infix and postfix notations is trivial.