Dijkstra算法和函数
问题是:假设我有一个用BNF指定的像sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B)这样的输入函数，我将使用递归下降算法解析输入，然后我如何使用或更改Dijkstra算法来处理这个给定的函数？我需要用sin | 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 编辑: Shunting Yard是将输入函数转换为RPN的算法，但我如何扩展它以接受另一个函数，如sin | cos | sqrt | ln？递归下降是否提供了对调车场所需的扩展？
回答 3
Stack Overflow用户
发布于 2010-06-01 22:23:48
我猜你说的是Dijkstra的Shunting Yard算法吧？
为了评估反向抛光符号(调车场的输出)，通常使用堆栈。
我相信Shunting Yard是用Algol设计的，我相信它应该可以与任何函数(固定或可变数量的参数)一起工作。
这里有一篇博客文章对此进行了更详细的解释：http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting-yard-algorithm-to-allow-variable-numbers-of-arguments-to-functions/
Stack Overflow用户
发布于 2010-06-01 20:59:43
我在这里没有看到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解释的那样。你永远不会停止学习新的东西！
Stack Overflow用户
发布于 2010-06-02 05:28:28
使用语法类似于Jack提供的语法的ANTLR。用多种语言创建一个好的解析器就足够了:Java/C/C++/Python/等。您应该使用ANTLRWorks来更快地验证表达式。
https://stackoverflow.com/questions/2949805
复制相似问题
腾讯云开发者
