Notation polonaise inversée

Lorsque l'on veut écrire une équation, la forme habituelle est d'utiliser une notation infixe du type 3*3. Le soucis avec cette notation, c'est que des parenthèse sont parfois nécessaires pour enlever toute ambiguïté. Par exemple: 3*3+2 ≠ 3*(3+2).
Le but de l'exercice est de créer un programme qui recevra un argument, une chaine de caractère contenant une expréssion en NPI qu'il faudra évaluer.

Définition

La notation polonaise inversée permet de se passer de parenthèse. C'est une notation postfixe: les opérandes sont fournies et ensuite on fournit l'opérateur. 3*3 devient donc 3 3 *. De ce fait, il est simple de distinguer 3*3+2 ≠ 3*(3+2) car 3*3+2 → 3 3 * 2 +, tandis que 3*(3+2) → 3 3 2 + *.

Traitement

Pour traiter ce genre de notation, il est nécessaire d'avoir une pile. Lorsqu'une valeur est rencontrée, alors celle-ci est ajoutée en haut de la pile. Lorsqu'un opérateur est rencontré, celui-ci s'applique sur les 2 valeurs en haut de la pile. Ces dernières seront donc retirée de la pile, puis la valeur calculée est ajoutée sur la pile.

Fonction de la bibliothèque standard

double strtod(const char *nptr, char **endptr);
La fonctions strtod() convertit la portion initiale de la chaîne pointée par nptr en un réel de type double.
Ces fonctions renvoient la valeur convertie si c’est possible.
Si endptr n’est pas NULL, un pointeur sur le caractère suivant le dernier caractère converti est stocké dans l’emplacement pointé par endptr.
Si aucune conversion n’est possible, la fonction renvoie zéro, et la valeur de nptr est stockée dans endptr.

Liste cyclique

On veut représenter nos données sous forme d'une liste liée cyclique, c'est-à-dire, le dernier élément de la liste est lié au premier élément de la liste. Les éléments de la liste sont des entiers.
Définir et implémenter des fonctions permettant d'ajouter un élément, retirer un élément et chercher si un élément est dans la liste cyclique.

struct cyclic_t{ int data; struct cyclic_t* next; }; typedef struct cyclic_t lc; //Cherche si la clé k est présente dans // la liste l //Renvoi vrai si la clé est présente // faux sinon bool cyclic_pres(int k, lc* l);

//Ajoute la clé k à la liste cyclique // pointée par l //Si l==NULL, alors une nouvelle liste // cyclique est crée //Renvoi vrai si l'ajout a été effectué // faux sinon bool cyclic_ajout(int k, lc** l); //Retire la cellule contenant la clé k // dans la liste pointée par l //Si la première cellule est modifiée, ce // changement est répercuté sur l //Renvoi vrai si la cellule a été retirée // faux sinon bool cyclic_retire(int k, lc** l);