algoritmo e funzioni di Dijkstra

Question

La domanda è: supponiamo di avere una funzione di ingresso come sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B) specificato con un BNF, io analizzare ingresso utilizzando l'algoritmo ricorsivo discesa, e poi come posso usare o algoritmo cambiamento di Dijkstra per gestire questa data funzione? Ho bisogno di eseguirlo con il peccato | cos | sqrt | ln, dove l'algoritmo di Dijkstra dovrebbe fare il lavoro.

EDIT: Può essere dovrei chiedere anche: Qual è il miglior pratica o struttura di dati per rappresentare data funzione?

EDIT: set di input può essere acquisita come:

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: Scalo di smistamento è l'algoritmo per convertire funzione di ingresso per RPN, ma come posso estenderla ad accettare un'altra funzione come il peccato | cos | sqrt | ln? Ha discesa ricorsiva fornisce tenuto estensione a Scalo di smistamento?

Answer 1

I presume che si sta parlando di Dijkstra Scalo di smistamento algoritmo?

Per valutare la notazione polacca inversa (uscita del fascio di smistamento), normalmente una pila viene utilizzata.

Scalo di smistamento è stato concepito per fare il parsing di Algol credo, e credo che si suppone che il lavoro con le funzioni (sia fissi o numero variabile di argomenti).

Ecco un post sul blog che spiega in modo più dettagliato: http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting- yard-algoritmo-to-allow-variabili-numeri-di-argomenti-to-funzioni /

Answer 2

non vedo Dijkstra qui, dal momento che è usato per trovare il percorso più breve in un grafico con i pesi non negativi.

Nel caso in cui si si parla di un parser discesa ricorsiva, che è di tipo LL (k) ed è definito da una grammatica simile a

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

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

la migliore struttura di dati per memorizzare questo tipo di informazioni di solito è un Abstract Syntax Albero che è un albero che replica la struttura del codice che analizza. In voi esempio, si avrebbe bisogno di una struttura differente o classe per vari pezzi di codice: BinaryOperation, Ident, Number, UnaryOperation, FunctionCall finire avere qualcosa di simile

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

EDIT: non sapeva che manovra-cantiere è stato inventato da Dijkstra! Tra l'altro si tratta di un algoritmo abbastanza facile come Moron spiegato .. si finisce mai di imparare qualcosa di nuovo!

Answer 3

ANTLR con una grammatica simile a quello fornito Jack. Dovrebbe essere sufficiente per creare una buona parser in più lingue: Java / C / C ++ / Python / etc. Leggi alcuni esempi e tutorial. Si dovrebbe usare ANTLRWorks per la verifica espressione più veloce.