Une introduction à l'algorithme de Shunting-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.
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.
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.
Exemples
Vous pouvez consulter mon repos Github ici qui est un bon exemple car c'est une calculatrice basique basé sur cet algorithme.
