Une introduction à l'algorithme de Shunting-Yard

Endroit ou l'on stocke les wagons pour les relier aux trains, qui est la définition littérale de Shuting-Yard.

Définition

L'algorithme de Shunting-Yard, est un algorithme (inventé par Edsger Dijkstra) permettant de parser des expressions mathématiques infixes vers des expressions postfixes, connu aussi sous le nom de notation polonaise inverse.

La parsing se fait sous cette forme:

ex: 5+6 (infix)
RPN: 5 6 + (postfix)

 

Explications

L'algorithme se base exclusivement sur les stack, qui est une structure de données respectant le principe LIFO.

Cas simple

Le principe est simple, prenons l'exemple de "3+4", on va parcourir tous les élements de cette string, ensuite on vérifie si l'element courant est un nombre ou un opérateur, si c'est un nombre, on l'ajoute directement dans la liste des elements parsés, sinon si c'est un opérateur on l'ajoute dans la stack des opérateurs (en respectant les priorités opératoires), puis on dépile tout pour le concatener à la liste des elements parsés.

Image explicative de l'article

Mais, cet algorithme est incomplet car il ne gère pas les priorités opératoires. Donc une opération de ce genre: (5+5*2/4-2)^2 sera mal parsé.

Cas complexes

Dans ce cas, on gère les priorités opératoires, notamment les parenthèses dans les expressions mathématiques. op_stack fait un peu office d'intermédiaire pour les opérateurs afin de garder en mémoire certains opérateurs et les dépiler quand ils auront une priorité operatoire plus grande que TOKEN. A la fin il se pourrait que des elements dans op_stack soit encore presents et donc on doit tout depiler en l'ajoutant a la liste de res.

Image explicative de l'article

Evaluation

Cet algorithme pourrait porter tout intêret à l'évaluation. C'est-à-dire le fait d'interpretrer l'expression parsé pour obtenir le résultat. En effet, utiliser Shunting-Yard pour parser des expressions mathematiques en notation polonaise inverse est interressant car on peut aisement évaluer une expression en notation polonaise inverse avec un simple algorithme.

Explications

Imaginons, l'expression parsé 5 6 +. On parcours tous les elements de cette expression , à commencer par 5, comme c'est un nombre on l'ajoute directement dans la stack, ensuite 6, on l'ajoute aussi dans la stack, et enfin l'opérateur + n'est pas un nombre donc on supprime les deux derniers elements de la stack pour le stocker dans une variable intermediaire, et ainsi l'évaluer avec l'element courant qui est l'opérateur.

Image explicative de l'article

Exemples

Vous pouvez consulter mon repos github ici qui est un bon exemple car c'est une calculatrice basique basé sur cet algorithme.

Merci d'avoir lu cet article, c'était mon premier article. J'attends vos retours :)


Dans la même catégorie :


Commentaires :

Génial, cependant, je m'attendais à des exemples étape par étape, avec des illustrations des stacks. Puis une petite partie implémentation python à la fin. Néanmoins l'explication reste claire. Ton écriture est très agréable :)
Jomtek
Super Ton Article ! Très bien expliqué, merci.
Natoons Miniature de l'utilisateur
Merci de vos retours. J'essayerais de faire encore mieux pour les prochaines fois ^^.
mortim Minature de l'utilisateur