我想编写一个 Java 解析器，将非标准形式 (NSF) boolean 函数转换为标准形式 (SF)。
NSF 示例:
A * B + D (A + B) C + A * B (A * B '+ A + B) D
要将 NSF 转换为 SF，您必须将括号相乘。上述函数的 SF 如下所示:A*B + D*A*C + D*B*C + A*B*A*B'*D + A*B*A*D + A* B*B*D
有人知道我该如何实现这个吗？
谢谢
最佳答案
您必须执行 4 个步骤才能实现您的目的:
1)使用“标准”(与您的术语无关)解析技术解析表达式，并生成相当于表示(已解析)表达式的 boolean 表达式树。
2) 将 boolean 代数规则应用于表达式树，将其从您不需要的表示形式转换为您想要的表示形式。您的“标准形式”似乎是合取范式(CNF)，因此您需要分配律代数规则来“乘以”乘积与总和(例如，a *(b + c))，以“摆脱括号”
3) 然后，您需要应用一些简化规则(例如，包含、取消)来消除多余的项，例如，a*b + a*b+c ==> a*b [a*b*c包含]，并且 a*b*a'+b*c ==> b*c [a*..a' 取消]。这只是更多的代数规则。
4) PrettyPrint 以人类可读的格式生成的代数术语。
您可以通过A)临时手工编码的递归下降解析和临时规则应用程序和 pretty-print 来编写所有这些，或者B)您可以获得解析器生成器(ANTLR很好)来进行解析，并进行规则操作通过临时方法，以及使用一些帮助(例如字符串模板或 C)的 PrettyPrint，您可以获得一个可以进行解析、构建树、应用您定义的代数规则并内置了 PrettyPrinting 的工具。
我们的DMS Software Reengineering Toolkit可以很好地完成案例C。您可以看到example of applying standard algebra rules that is a direct analog to your problem .
真正难以解决的问题之一是处理代数中的结合性和交换性，例如，知道 A*B*A' 是“假”是代数规则 X*X'=> 的结果false，但您不能直接检查代数规则中的模式。您必须应用考虑交换性的代数规则。对于结合性的同样的论证。 DMS 做得很好的事情之一就是为您处理这个问题，如果您声明适当的运算符来具有这些属性。您可以在示例中看到这一点。
唉，不是用 Java 编码的。
关于java - java中将非标准形式解析为标准形式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9844023/