英文:
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论