L'algorithme et les fonctions de Dijkstra

Question

la question est la suivante: supposons que j'ai une fonction d'entrée comme sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B) spécifiée avec une BNF, je parse entrée en utilisant l'algorithme de descente récursive, et comment puis-je utiliser ou l'algorithme de changement Dijkstra pour gérer cette fonction donnée? Je dois l'exécuter avec le péché | cos | sqrt | Dans, où l'algorithme de Dijkstra devrait faire le travail.

EDIT: Peut être je demande: Quelle est la meilleure pratique ou une structure de données pour représenter la fonction donnée?

EDIT: jeu d'entrée peut être acquise:

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: Yard est l'Manœuvres algorithme pour convertir la fonction d'entrée RPN, mais comment puis-je l'étendre à accepter une autre fonction comme le péché | cos | sqrt | Dans? Est-ce que la descente récursive fournit nécessaire extension de triage?

Answer 1

Je suppose que vous parlez de Dijkstra algorithme de triage?

Pour évaluer la notation polonaise inverse (sortie de gare de triage), normalement une pile est utilisée.

Cour a été conçu Manœuvres pour faire l'analyse syntaxique dans Algol je crois, et je crois qu'il est censé fonctionner avec toutes les fonctions (soit nombre fixe ou variable d'arguments).

Voici un blog qui explique plus en détail: http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting- cour-allow-variable-à-algorithme de numéros à des arguments-fonctions /

Answer 2

Je ne vois pas Dijkstra ici, car il est utilisé pour trouver le chemin le plus court dans un graphique avec des poids non négatifs.

En cas vous parlez d'un analyseur de descente récursive, qui est de type LL (k) et il est défini par une grammaire similaire à

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

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

la meilleure structure de données pour stocker ce type d'information est habituellement un arbre de syntaxe abstraite qui est un arbre qui reproduit la structure du code analysée. Vous par exemple vous auriez besoin d'une struct différente ou classe pour différents morceaux de code: BinaryOperation, Ident, Number, UnaryOperation, FunctionCall se retrouver avec quelque chose comme

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

EDIT: Je ne savais pas que shunter verges a été inventé par Dijkstra! Par la façon dont il est un algorithme assez facile comme expliqué Moron .. vous ne serez jamais cesser d'apprendre quelque chose de nouveau!

Answer 3

ANTLR avec une grammaire semblable à celui fourni Jack. Il devrait être suffisant pour créer un bon analyseur en plusieurs langues: Java / C / C ++ / Python / etc. Lisez quelques exemples et des tutoriels. Vous devez utiliser ANTLRWorks pour la vérification d'expression plus rapide.