Dijkstra的算法和功能

Question

问题是：假设我有一个输入函数 sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B) 用BNF指定，我将使用递归下降算法解析输入，然后如何使用或更改Dijkstra的算法来处理此给定功能？我需要用罪执行它| cos | sqrt | 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 

编辑：分流码是将输入功能转换为RPN的算法，但是如何将其扩展到接受其他功能，例如SIN | cos | sqrt | ln？递归下降是否为分流院子提供了所需的扩展？

Answer 1

我想你在谈论dijkstra的 分流院子 算法？

为了评估反向抛光符号（分流码的输出），通常使用堆栈。

我相信划分院子是为了在阿尔戈尔进行解析，我相信它应该使用任何功能（固定数量或可变的参数）。

这是一篇博客文章，可以更详细地解释它： http://www.kallisti.net.nz/blog/2008/02/extension-to-te-te-the-the-shunting-yard-algorithm-to-allable-variable-numbers-numbers-numbers-of-arguments-to-functions/

Answer 2

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

在您的情况下，您谈论递归血统解析器，那是善良的（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

编辑：不知道Shunting-Yard是由Dijkstra发明的！顺便说一句，这是一种非常简单的算法，就像Moron所解释的。.您永远不会停止学习新事物！

Answer 3

利用 antlr 语法类似于提供的杰克。用多种语言创建一个好的解析器应该足以：Java/c/c/c ++/python/等。阅读一些示例和教程。您应该使用 Antlrworks 用于更快的表达验证。