Dijkstra的算法和函数

发布于 2024-09-03 12:46:54 字数 551 浏览 3 评论 0原文

问题是：假设我有一个像 sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B) 这样用 BNF 指定的输入函数，我将使用递归下降算法解析输入，然后如何使用或更改 Dijkstra 算法来处理这个给定的函数？我需要用 sin 来执行它 | 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 |开方|在？递归下降是否提供了调车场所需的扩展？

原文

the question is: suppose I have an input function like sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B) specified with a BNF, I will parse input using recursive descent algorithm, and then how can I use or change Dijkstra’s algorithm to handle this given function? I need to execute it with sin | cos | sqrt | ln, where Dijkstra’s algorithm should do the work.

EDIT: May be I should ask also: What is the best practice or data structure to represent given function?

EDIT: Input set can be acquired as:

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

EDIT: Shunting Yard is the algorithm to convert input function to RPN, but how can I extend it to accept another function like sin | cos | sqrt | ln? Does recursive descent provides required extension to Shunting Yard?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

生死何惧 2024-09-10 12:46:54

我想您正在谈论 Dijkstra 的 Shunting Yard 算法？

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

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

这是一篇博客文章，更详细地解释了它：http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting-yard-algorithm -允许函数参数的变量数量/

回复收藏 0 原文

你丑哭了我 2024-09-10 12:46:54

我在这里没有看到 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 code>，FunctionCall 最终有类似的内容

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

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

I don't see Dijkstra here, since it is used to find the shortest path in a graph with non negative weights.

In you case you talk about a recursive descent parser, that is of kind LL(k) and it is defined by a grammar similar to

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

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

the best data structure to store this kind of information usually is an Abstract Syntax Tree that is a tree which replicates the structure of the code it parses. In you example you would need a different struct or class for various pieces of code: BinaryOperation, Ident, Number, UnaryOperation, FunctionCall ending up having something like

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

EDIT: Didn't know that shunting-yard was invented by Dijkstra! By the way it's a quite easy algorithm like Moron explained.. you'll never stop learning something new!

回复收藏 0 原文