Dijkstra’s algorithm and functions

Question

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?

Answer 1

I presume you are talking about Dijkstra's Shunting Yard algorithm?

To evaluate the reverse polish notation (output of shunting yard), normally a stack is used.

Shunting Yard was devised to do the parsing in Algol I believe, and I believe it is supposed to work with any functions (either fixed or variable number of arguments).

Here is a blog post which explains it in more detail: http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting-yard-algorithm-to-allow-variable-numbers-of-arguments-to-functions/

Answer 2

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!

Answer 3

Use ANTLR with a grammar similar to the one Jack provided. It should be enough to create a good parser in multiple languages: Java/C/C++/Python/etc. Read some example and tutorials. You should use ANTLRWorks for faster expression verification.