5

我有一个问题在于比较布尔表达式( OR 是 +,AND 是 * )。更准确地说,这里是一个例子:

我有以下表达式:“A+B+C”,我想将它与“B+A+C”进行比较。像字符串一样比较它不是解决方案 - 它会告诉我表达式不匹配,这当然是错误的。关于如何比较这些表达式的任何想法?

关于如何解决这个问题的任何想法?我接受任何类型的建议,但(作为注释)我的应用程序中的最终代码将用 C++ 编写(当然接受 C)。

一个正常的表达式也可以包含括号:

(A * B * C) + DA+B*(C+D)+X*Y

提前致谢,

尤利安

4

2 回答 2

9

我认为穷举(并且可能穷举)创建真值表的竞争方法是将所有表达式简化为规范形式并进行比较。例如,用一些关于符号排序(例如术语中的字母顺序)和术语(例如术语中的第一个符号的字母顺序)的规则将所有内容重写为合取范式。这当然要求一个表达式中的符号 A 与另一个表达式中的符号 A 相同。

编写(或从网上获取)用于将表达式重写为 CNF 的 C 或 C++ 函数有多容易,我不知道。但是,有很多 AI 工作是用 C 和 C++ 完成的,所以当你用谷歌搜索时,你可能会发现一些东西。

我也有点不确定这种方法和真值表方法的比较计算复杂度。我强烈怀疑它是一样的。

无论您使用真值表还是规范表示,您当然可以通过根据输入表单包含的不同符号的数量将输入表单分成组来减少要完成的工作。

编辑:在阅读其他答案时,特别是生成所有真值表并比较它们的建议,我认为@Iulian 严重低估了可能的真值表的数量。

假设我们决定使用 RPN 来编写表达式,这将避免必须处理括号,并且有 10 个符号,这意味着 9 个(二进制)运算符。会有10个!符号的不同顺序,以及 2^9 种不同的运算符顺序。因此将有 10 个!x 2^9 == 此表达式的真值表中有 1,857,945,600 行。这确实包括一些重复项,例如,任何仅包含“and”和“or”的表达式都将是相同的,而不管符号的顺序如何。但我不确定我能不能更进一步......

还是我犯了一个大错误?

于 2010-06-03T12:08:18.017 回答
8

您可以计算所有可能输入的每个表达式的真值表,然后比较真值表。

于 2010-06-03T11:43:22.357 回答