Concept
Lalgorithme 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. 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. 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
