Match two nested logical AND OR expression tree objects

Question

I need to compare a given logical expression with another in java, to identify if both are the same. For example, consider an expression as ((a&b)&(c|d)&(e&f)) and other as ((a&e)&(c|d)&(b&f)), they both are equivalent. Consider (a&(f&(b&e))&(c|d)): this is also equivalent. Furthermore, this expressions can be nested. I thought of converting this to prefix notations, but can't find a proper way through. Expressions is a recursive class object with expression-type as AND/OR and an array of it's child expressions ex. for above first expression:

{
    type: AND,
    expressions: [{
        type: AND,
        expressions: [{
            type: SIMPLE,
            expression: [a]       <-- this could also be nested if type would have been logical
        }, {
            type: SIMPLE,
            expression: [b]
        }]
    }, {
        type: OR,
        expressions: [{
            type: SIMPLE,
            expression: [c]
        }, {
            type: SIMPLE,
            expression: [d]
        }]
    }, {
        type: AND,
        expressions: [{
            type: SIMPLE,
            expression: [e]
        }, {
            type: SIMPLE,
            expression: [f]
        }]
    }]
}

Is there any way to simplify expressions and compare them?

Answer 1

You can use the "boolean.py" module to do this. If you want to try it, there's a bit of a trick. You need to install via "pip install boolean.py" vs "pip install boolean". They're two different packages, and you want the '.py' version.

Here's looking at your examples, and a failure case that I added as well:

import boolean
algebra = boolean.BooleanAlgebra()
expr1 = algebra.parse("((a&b)&(c|d)&(e&f))").simplify()
expr2 = algebra.parse("((a&e)&(c|d)&(b&f))").simplify()
expr3 = algebra.parse("(a&(f&(b&e))&(c|d))").simplify()
print(expr1 == expr2)
print(expr1 == expr3)

expr4 = algebra.parse("(a&(f&(b&e))&(c|d)&(x|y))").simplify()
expr5 = algebra.parse("(a&(f&(b&e))&(c|y)&(x|d))").simplify()

print(expr4 == expr5)

Result:

True
True
False