首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在java中将非标准格式解析为标准格式

问在java中将非标准格式解析为标准格式
EN

Stack Overflow用户
提问于 2012-03-24 01:44:10
回答 1查看 411关注 0票数 2

我想编写一个Java解析器,将非标准格式(NSF)布尔函数转换为标准格式(SF)。

NSF示例:

代码语言:javascript
复制
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

有没有人知道我该如何实现它?

谢谢

EN

回答 1

Stack Overflow用户

发布于 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编写的。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/9844023

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档