Convertisseur de chaine infixes en postfixes


Salut à tous 😉 Aujourd’hui, je vais vous proposer de créer un convertisseur de chaine infixe, en chaine postfixe.

Il s’agit de mon premier billet utile pour mes élèves anonymes qui grâce à google & cie arriverons sur cette page dans l’unique but d’extirper mes connaissances 🙂

Évidemment, ce n’est pas un tuto donc faut réfléchir un minimum avant de pouvoir utiliser ces infos, et surtout les comprendre !

1) Infixe, Postfixe.. C’est quoi ??

Il s’agit d’un procédé utilisé pour pouvoir résoudre une opération mathématique « humainement compréhensible » à l’aide d’un ordinateur, ou toutes autres machines qui auraient besoin d’algorithmes de résolution statique. (Perso, pardonnez moi mon ignorance, mais à par l’ordinateur, j’en connais aucun ^^).

Ainsi un calcul humainement compréhensible (Infixe) ressemblerait à ça : (6 + 2) * 5 – 8 / 4. Son équivalent  postfixe serait : 6 2 + 5 * 8 4 / –. Mais non, c’est pas vraiment complexe comme notation… C’est même très simple à concevoir un algorithme capable de résoudre une chaine postfixe parce que la résolution du calcul se fait statiquement, de gauche à droite. Alors qu’une chaine infixe doit constamment être lu d’endroits différent pour respecter les règles de priorités.

Hé oui, une chaine postfixe présente toujours ses opérandes à gauche, et l’opérateur à droite. La résolution du calcul devient alors aisée :

2) Cool, on commence ? 😛

Ouais, pas de problèmes 😉 Mais avant faut déjà voir comment on va faire tout ça. Et surtout quelles techniques utiliser 🙂 Pour pouvoir contenir les chaines, je vous proposes une façon simple et efficace : les piles 8)

Après un autre détail au quel il faut faire vraiment très attention : c’est la conversion de la chaine de caractère : char* lue par le programme, en pile d’entier : int ! En effet, le type de variable char étant codé sur un seul octet, et étant une variable signée (c’est a dire qui peut contenir un nombre positif et négatif) le nombre ne sera contenu que sur 7 bits, soit une valeur maximale de 2e7 soit de 128, ce qui briderait quand même bien le programme. Pour justifier ce que je raconte, je vous propose de tester vous même ce que ça donne :

char variableTest = 200;
std::cout << variableTest; 
//Retour console : -101

Ahh oui, n’oubliez pas aussi de négliger les espaces que l’utilisateur pourrait mettre dans le calcul aussi. Ça polluerais la pile avec des conneries inutiles 🙂

3) Gérer les nombres à plusieurs chiffres

Hé oui ! 12 + 5 représente un tableau de 6 chars. On enlèves les espaces négligés, on tombe à 4. Le problème, c’est qu’il n’y a réellement que trois objet différent dans ce calcul : 12, soit deux chars doivent être fusionnés en un seul int pour obtenir réellement le chiffre douze. Pour cela je vous propose une lecture de la chaine de caractère, de gauche à droite et de contenir tout les nombres lu dans une autre pile. Ensuite dès que la lecture atteins un opérateur, une boucle de calcul permettrais de retrouver le nombre exacte dans un entier, et plus dans un tableau de caractère 🙂 Voici ce que ça donne chez moi :

do {
 tamponNombre.insererEnTete(charTraite - '0');
 chaineInfixe.retirerEnTete();
 charTraite = chaineInfixe.getTete();
 } while ((charTraite >= '0') && (charTraite <= '9') && (!chaineInfixe.estVide()));

Ici, tamponNombre et chaineInfixe sont deux piles. La première contient tout les caractères que comporte le chiffre en cours de lecture (Notez que ce sont bien des chars qui sont écrits ici, mais contenant la réelle valeur numérique du chiffre, et pas son équivalent en ASCII. Cela est réalisé à l’aide du -‘0’. Si vous ne comprenez pas, réfléchissez un peu, ou faites des tests, je suis sur que vous y arriverez 😉 ). La seconde pile contient l’entrée infixe brute entrée par l’utilisateur du programme.

Une fois la lecture d’un opérateur en cours, la pile tamponNombre doit être déchargée et contenue dans une nouvelle chaine d’entier, celle qui sera utiliser pour pouvoir effectuer le calcul.

int resultat = 0;
for (int i = 1; !tamponNombre.estVide(); i*=10)
{
	resultat += tamponNombre.getTete() * i;
	tamponNombre.retirerEnTete();
}

Il ne reste plus qu’à injecter resultat dans une pile d’entier qui contiendra la chaine infixe  😉

4) Gérer les opérateurs

Rassurez vous, il n’y a rien de bien compliqué ici, mais quand même une petite subtilité à ne surtout pas négliger : la fiabilité de votre convertisseur en dépend ! Pour gérer les opérateurs en entier, il ne s’agit pas uniquement de claquer un int operateurAInsererDansLaPileDEntier = ‘+’. Hé oui ! Les correspondance ASCII étant des nombres entier positif, on n’aurait aucun moyen de différencier le signe plus (+), par exemple qui vaut 43 et le réel nombre 43 ! Ainsi une chaine 43 + 5 serait convertie en 43 43 5, pas cool 😡

Un moyen de faire face au problème est de stocké les opérateurs sous forme négative c’est à dire qu’on ferait int operateurAInsererDansLaPileDEntier = ‘+’ * -1. La précédente chaine de caractères 43 + 5 serait alors stockée sous forme de pile d’entier en 43 -43 5, ce qui permet de faire la différence entre les opérateurs et les nombres ! 🙂

Tsss, le premier qui me sors « Et on fait comment avec les nombres négatifs ?? » je lui envois une pastèque dans la tête >< (Pardonnez mon manque d’inventivité). Bah oui, l’opérateur de différence sera convertis comme tout les autres en entier, et les deux opérandes qu’il possède en entier positif, comme n’importe quels autres. On aura alors : 20 – 5 convertis en 20 -45 5.

5) Convertir la chaine infixe, en chaine postfixe

Nous voici au cœur de ce cour : ça raison d’être 😀 Quels sont les procédés à suivre pour pouvoir déplacer les différents éléments de notre chaine infixe en chaine postfixe correcte ? Aller, je vais être gentil avec vous, et vous dire tout ça 🙂

~ Poussez une parenthèse gauche ‘(‘ sur une pile de traitement.
~ Ajoutez une parenthèse droite ‘)’ à la fin de la pile infix.
~ Ajoutez un carractère de fin de chaine ‘\0’ dans postfixe. (Je vous expliquerais plus tard pourquoi ;))
~ Tant que la pile de traitement n’est pas vide, lire infix de gauche à droite et :
~ ~ Si le caractère en cours de lecture est un chiffre :
~ ~ ~ L’écrire cash dans la pile postfixe.
~ ~ Si le caractère en cours de lecture est une paranthèse gauche :
~ ~ ~ La déposer dans la pile de traitement.
~ ~ Si le caractère est un opérateur :
~ ~ ~ Retirer tout les opérateurs au sommet de la pile de traitement tant qu’ils ont une présence égale ou supérieur à l’opérateur en cours et les insérés dans postfixe.
~ ~ ~ Ecrire le carractère lue dans la pile de traitement.
~ ~ Si le caractère est une parenthèse droite :
~ ~ ~ Retirer tout les opérateurs de la pile de traitement et les mettres dans la pile postfixe jusqu’à ce qu’on tombe sur une parenthèse gauche.
~ ~ ~ Retirer et éliminer la parenthèse gauche de la pile de traitement. (Ne pas commettre cet oublie vous épargnera quelques heures de debug 😀 )
~ Retirer l’élément en cours de lecture de infixe et passer au suivant.

Et voila, après tout cas, vous devez obtenir une parfaite pile d’entier postfixée. Avec l’exemple précédent : (6 + 2) * 5 – 8 / 4 vous devriez retourner : 6 2 -43 5 -42 8 4 -47 -45. Il ne reste maintenant, plus qu’à résoudre ce calcul 🙂

6) La résolution du calcul

Comme dit précédemment, ce n’est pas bien compliqué, il suffit de stocker les nombres lu dans une autre pile (ouais je sais, j’aime les piles :p) et de produire un calcul simple en fonction d’un opérateur lu. C’est réalisable en injectant un caractère reconnaissable à la fin de la chaine postfixée, et de rester dans la boucle tant que ce caractère n’es pas atteins. C’est le rôle justement du ‘\0’ insérée avant :p On obtient alors un algorithme qui peut ressembler à ça :

~ Tant que le carractère de fin de chaine ‘\0’ n’est pas attend, lire la chaine postfixe.
~ ~ Si le nombre traité est positif :
~ ~ ~ L’inscrire dans une pile de traitement.
~ ~ Si le nombre traité est négatif :
~ ~ ~ Le rendre positif.
~ ~ Si le nombre correspond à une valeur ASCII d’un opérateur :
~ ~ ~ Garder en mémoire les deux dernier nombres de la pile de traitement.
~ ~ ~ Appliquer l’opérateur.
~ ~ ~ Retourner le résultat dans la pile de traitement.
~ ~ Retirer l’élément en cours de lecture de postfixe et passer au suivant.

Hé voila, le tour est joué ! Vous obtiendrez comme premier élément de la pile de traitement, la valeur de la chaine postfixée qu’il y avait avant le passage de la boucle 😀 Reprenons l’exemple d’avant : 6 2 -43 5 -42 8 4 -47 -45 retourne dans la pile de traitement : 38 😉

S’en est fini pour ce premier cour. J’espère qu’il vous aura plus, et que vous l’avez compris un minimum 🙂 J’explique très mal apparemment, bonne chance à vous donc. :-\ Certes, c’est pas gagné, mais on doit pouvoir s’en sortir ! Aller courage, vous finirez bien par « voir la lumière » un jour ou l’autre 😀

A++, amusez vous bien 😎


Une réponse à “Convertisseur de chaine infixes en postfixes”