0

问题是：假设我有一个sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B)使用 BNF 指定的输入函数，我将使用递归下降算法解析输入，然后如何使用或更改 Dijkstra 的算法来处理这个给定的函数？我需要用罪来执行它 | COS | 平方 | ln，Dijkstra 的算法应该在其中完成工作。

编辑：也许我还应该问：表示给定功能的最佳实践或数据结构是什么？

编辑：输入集可以获取为：

C 0.01 .01 .02 .04 .08 .02 .02 .04 
A .016 .008 .116 .124 .147 .155 .039 .023  
D .012 .025 .05 .1 .1 .1 .025 .012000 .012
B .007 .007 .015 .022 .029 .036 .044 .051 .058 .066 .073 .080

编辑：Shunting Yard 是将输入函数转换为 RPN 的算法，但是如何扩展它以接受另一个函数，如 sin | COS | 平方 | 吗？递归下降是否为调车场提供了所需的扩展？

4

3 回答 3

3

我想你在谈论 Dijkstra 的Shutting Yard算法？

为了评估反向波兰符号（调车场的输出），通常使用堆栈。

我相信，Shunting Yard 被设计用于在 Algol 中进行解析，并且我相信它应该适用于任何函数（固定或可变数量的参数）。

这是一篇更详细地解释它的博客文章：http ://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting-yard-algorithm-to-allow-variable-numbers-参数到函数/

于 2010-06-01T14:23:48.107 回答
0

我在这里看不到 Dijkstra，因为它用于在具有非负权重的图中找到最短路径。

在您的情况下，您谈论的是递归下降解析器，即 LL(k) 类型，它由类似于以下的语法定义

expression ::= term + term | term - term
term ::= factor * factor | factor / factor
factor ::= ident | number

number ::= digit | digit number
digit ::= 0 | 1 | 2 ...

存储此类信息的最佳数据结构通常是抽象语法树，它是一棵复制其解析的代码结构的树。在你的例子中，你需要一个不同的结构或类来处理各种代码：BinaryOperation, Ident, Number, UnaryOperation,FunctionCall最终有类似的东西

                         BinaryOperation +
                          |            |
                                     BinaryOperation *
                                      |            |
                                    Number       BinaryOperation +
                                      |           |
                                     0.756     BinOp *
                                               |    |
                                             Ident Ident
                                               |    |
                                               C    D

编辑：不知道调车场是由 Dijkstra 发明的！顺便说一句，就像 Moron 解释的那样，这是一个非常简单的算法。你永远不会停止学习新东西！

于 2010-06-01T12:59:43.190 回答
0

使用类似于 Jack 提供的语法的ANTLR 。用多种语言创建一个好的解析器就足够了：Java/C/C++/Python/等。阅读一些示例和教程。您应该使用ANTLRWorks进行更快的表达式验证。

于 2010-06-01T21:28:27.907 回答