匹配两个嵌套的逻辑AND OR表达式树对象。

huangapple go评论62阅读模式
英文:

Match two nested logical AND OR expression tree objects

问题

我需要在Java中将给定的逻辑表达式与另一个表达式进行比较,以确定它们是否相同。
例如,考虑一个表达式为((a&b)&(c|d)&(e&f)),另一个表达式为((a&e)&(c|d)&(b&f)),它们是等价的。再考虑(a&(f&(b&e))&(c|d)):这也是等价的。此外,这些表达式可以是嵌套的。我考虑过将其转换为前缀表示法,但无法找到适当的方法。
表达式是一个递归的类对象,其表达式类型为AND/OR,具有其子表达式的数组。
例如,对于上面的第一个表达式:

{
    type: AND,
    expressions: [{
        type: AND,
        expressions: [{
            type: SIMPLE,
            expression: [a]       <-- 如果类型是逻辑的话这也可以是嵌套的
        }, {
            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]
        }]
    }]
}

是否有简化表达式并比较它们的方法呢?

英文:

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?

答案1

得分: 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
英文:

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

huangapple
  • 本文由 发表于 2020年10月18日 05:26:25
  • 转载请务必保留本文链接:https://go.coder-hub.com/64407512.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定