我想编写一个Java解析器,将非标准格式(NSF)布尔函数转换为标准格式(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
有没有人知道我该如何实现它?
谢谢
发布于 2012-03-26 13:59:23
你必须做4个步骤来达到你的目的:
1)使用“标准”(与您的术语无关)解析技术解析表达式,并生成相当于表示(解析的)表达式的布尔表达式树。
2)将布尔代数规则应用于表达式树,将其从您不想要的表示形式转换为您想要的表示形式。您的“标准形式”似乎是合取范式(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)特殊的手工编码的递归下降解析和特殊的规则应用程序和漂亮的打印,或者B)你可以得到一个解析器生成器(ANTLR很好)来做解析,通过特别的方法做规则操作,并且漂亮打印使用一些帮助,如字符串模板,或者C)你可以得到一个工具来做解析,构建树,将应用你定义的代数规则,并内置漂亮的打印。
我们的DMS Software Reengineering Toolkit可以很好地处理case C。您可以看到一个example of applying standard algebra rules that is a direct analog to your problem。
其中一个很难解决的问题是在代数中处理结合性和交换性,例如,知道A*B*A‘是" false“是代数规则X*X'=> false的结果,但您不能直接检查代数规则中的模式。你必须应用考虑通用性的代数规则。结合性也有同样的论据。DMS做得很好的一件事就是为您处理它,如果您声明适当的运算符来拥有这些属性的话。您可以在示例中看到这一点。
可惜,不是用Java编写的。
https://stackoverflow.com/questions/9844023
复制相似问题