Algorithme Shunting-yard
L'algorithme Shunting-yard (littéralement, "algorithme de la gare de triage") est une méthode d'analyse syntaxique d'une expression mathématique exprimée en notation algébrique parenthésée. Il peut être utilisé pour traduire l'expression en notation polonaise inverse, ou en arbre syntaxique abstrait. Il a été inventé par Edsger Dijkstra.
Principe de conversion
Comme l'évaluation de NPI, la conversion de la notation d'infixe en NPI est fondée sur l’utilisation d’une pile. Les expressions d’infixe sont la forme de mathématique que la plupart des personnes utilisent habituellement, comme 3+4 ou 3+4×(2-1).
Pour la conversion il y a 2 variables texte (chaîne de caractères), l’entrée et la sortie. Il y a également une pile pour empiler les opérateurs pas encore ajoutés à la chaîne de sortie. Pour convertir, le programme lit chaque lettre dans l’ordre et réalise l’opération liée à cette lettre.
Une conversion simple
- l’entrée : 3+4
- ajouter 3 Ă la sortie
- empiler l'opération + sur la pile des opérateurs
- ajouter 4 au résultat précédent
- dépiler tous les opérateurs restants sur la sortie
- la sortie : 3 4 +
Ce simple exemple nous montre les règles suivantes :
- Sans fonctions ni opérateurs plus complexes, tous les opérandes se retrouvent au début de la sortie
- Les opérateurs à plus grande priorité se trouvent plus près du début de la sortie.
Description de l’algorithme de conversion
- tant qu’il y a des tokens à lire :
- lire le token.
- si c’est un nombre l’ajouter à la sortie.
- si c'est une fonction, le mettre sur la pile.
- si c'est un séparateur d'arguments de fonction (par exemple une virgule) :
- jusqu'à ce que l'élément au sommet de la pile soit une parenthèse gauche, retirer l'élément du sommet de la pile et l'ajouter à la sortie. Si toute la pile est dépilée sans trouver de parenthèse gauche, c’est qu’il y a un mauvais parenthésage.
- si c’est un opérateur o1 alors
- 1) tant qu’il y a un opérateur o2 sur le haut de la pile et si l’une des conditions suivantes est remplie.
- o1 est associatif ou associatif à gauche et sa priorité est inférieure ou égale à celle d’o2, ou
- o1 est associatif à droite et sa priorité est inférieure à celle d’o2,
- retirer o2 de la pile pour le mettre dans la sortie
- 2) mettre o1 sur la pile
- si le token est une parenthèse gauche, le mettre sur la pile.
- si le token est une parenthèse droite, alors dépiler les opérateurs et les mettre dans la sortie jusqu’à la parenthèse gauche qui elle aussi sera dépilée, mais pas mise dans la sortie. Après cela, si le token au sommet de la pile est une fonction, le dépiler également pour l'ajouter à la sortie. Si toute la pile est dépilée sans trouver de parenthèse gauche c’est qu’il y a un mauvais parenthésage.
- lire le token.
- après la lecture du dernier token, s'il reste des éléments dans la pile il faut tous les dépiler pour les mettre dans la sortie (il ne doit y avoir que des opérateurs. Si on trouve une parenthèse gauche alors il y a eu un mauvais parenthésage).