Calculatrice en notation polonaise inversée : acte I

La notation polonaire inversée (ou Reverse Polish Notation) a été popularisée par les calculatrices HP : il s'agit d'une notation suffixe présentant l'avantage de ne pas nécessiter de parenthésage. Ainsi par exemple, l'expression arithmétique notée de façon infixe (3 + 4) * (3 - 2) est exprimée en notation suffixe par 3 4 + 3 2 - *.

On pourra s'entraîner à représenter l'arbre d'expression ainsi que la notation suffixe des expressions infixes suivantes :

• 2+20*2
• 2*(10*2+1)
• 10 + 20 + 12
• (10 + 4/2)*2+(3*3*(4/2))

Une pile est une structure gérée par deux opérations primitives :

• L'empilement d'un élément : cette opération ajoute l'élément en haut de pile
• Le dépilement d'un élément : cette opération permet de récupérer l'élément en haut de pile. Une pile est ainsi qualifiée de structure LIFO (Least In, First Out) : l'élément ajouté le plus tardivement est celui qui est récupéré le premier (contrairement à une file).

Afin d'évaluer les expressions fournies par l'utilisateur en notation suffixe, nous utilisons une pile. Chaque nombre entré est empilé dans celle-ci. La rencontre d'un opérateur conduit au dépilement des opérandes, à la réalisation de l'opération puis à l'empilement du résultat.

On écrira une structure générique de pile ainsi que les fonctions nécessaires pour son allocation, sa libération ainsi que l'empilement et le dépilement d'élément. On fera attention à gérer les erreurs potentielles (sous-capacité ou sur-capacité de la pile). La capacité de la pile est précisée à l'exécution lors de son allocation.

Écrire une calculatrice récupérant le flux de lexèmes en notation suffixe (nombres et opérateurs arithmétiques élémentaires) sur l'entrée standard et réalisant les opérations demandées par manipulation d'une pile associée. On précise que chaque lexème est séparé par au moins un caractère d'espacement. Ainsi l'expression en notation suffixe 3 -2 * réalise l'opération (en notation infixe) 3 * (-2) tandis que l'expression suffixe 3 - 2 * est invalide (l'opération binaire - entraînant un dépilement de deux opérandes alors que la pile n'en contient qu'une).

Réaliser un fichier Makefile (utilisé par l'outil de construction de programmes Make) afin de compiler les modules nécessaires à l'obtention de l'exécutable de calculatrice.

Il est nécessaire d'être attentif à la gestion des erreurs potentielles. L'utilisateur doit pouvoir communiquer des entrées invalides : celles-ci doivent provoquer l'affichage d'un message d'erreur compréhensible et en aucun cas ne doivent déclencher des accès mémoire illicites (erreur de segmentation). Pour le déverminage gdb ainsi que valgrind pour détecter les problèmes de mémoire sont d'une grande utilité.

Pour la lecture de lexèmes, les fonctions de la famille *scanf sont conseillées.

Pour la gestion des nombres, on pourra s'inspirer du type suivant pouvant contenir un entier ou un flottant :

			struct _nombre { 
				enum _type { ENTIER, FLOTTANT } type; 
				union _valeur { int entier; float flottant; } valeur; 
			};
		

On pourra réécrire des fonctions implantant des opérateurs arithmétiques sur les struct _nombre, l'objectif étant de retourner un résultat entier si tous les opérandes sont des entiers (par exemple 10/3=3) ; dans le cas contraire, on retourne un flottant (e.g. : 10.0/3=3.333....). On pourra également implanter de nouveaux opérateurs.