algoritmo e funzioni di Dijkstra
-
05-10-2019 - |
Domanda
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?
Soluzione
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 /
Altri suggerimenti
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!
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.