Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section «Notes et références».
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.
Une conversion simple
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.
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.
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.
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.
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).
