Сопоставьте два вложенных объекта дерева логических выражений И ИЛИ

Question

Мне нужно сравнить данное логическое выражение с другим в java, чтобы определить, одинаковы ли оба. Например, рассмотрим выражение как ((a&b)&(c|d)&(e&f)) и другие как ((a&e)&(c|d)&(b&f)), они оба эквивалентны. Рассматривать (a&(f&(b&e))&(c|d)): это тоже эквивалентно. Кроме того, эти выражения могут быть вложенными. Я думал преобразовать это в префиксную нотацию, но не могу найти правильный способ. Выражения - это рекурсивный объект класса с типом выражения как И / ИЛИ и массивом его дочерних выражений ex. для первого выражения выше:

{
    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]
        }]
    }]
}

Есть ли способ упростить выражения и сравнить их?

Answer 1

Для этого вы можете использовать модуль boolean.py. Если вы хотите попробовать, есть небольшая хитрость. Вам необходимо установить через "pip install boolean.py" против "pip install boolean". Это два разных пакета, и вам нужна версия.py.

Вот ваши примеры, а также случай сбоя, который я добавил:

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)

Результат:

True
True
False