Exercice

Bonjour,
je demande SVP la solution de cette exercice.


Département D’informatique
2ème Année LISI
2008/2009
Mini-projet en Algorithmique et structure de données II

Directives
Ce mini-projet a pour but d’expérimenter la manipulation des structures dynamiques : listes chaînées, piles et files, il peut être réalisé en binôme ou en monôme.
Le programme doit être développé en langage C++
Le programme doit être accompagné d’un rapport ne dépassant pas 3 pages
La date de remise de ce travail est le 05/05/2009.

Introduction
Ce mini projet se compose de 3 parties
1- l’évaluation des expressions mathématiques en notation polonaise suffixée.
2- la traduction des expressions mathématiques ordinaires en notation polonaise suffixée.
3- l’évaluation des expressions mathématiques ordinaires

Partie I : évaluation de l’expression exprimée en notation polonaise suffixée.

La notation polonaise est une manière pour écrire des expressions arithmétiques en s’affranchissant des parenthèses. Le tableau suivant explique le passage d’une expression mathématique ordinaire vers une expression en notation polonaise :


Notation courante A+B A-B A*B A/B
Notation polonaise préfixée +AB -AB *AB /AB
Notation polonaise suffixée AB+ AB- AB* AB/

Exemple :
4+3 s’écrit en notation polonaise suffixée 4 3 +
(2+5)*4 s’écrit en notation polonaise suffixée 2 5 + 4 *
(2-17)*(3/(10-5)) s’écrit en notation polonaise suffixée 2 17 - 3 10 5 - / *


a) Entraînez vous sur les exemples suivants (les écrire en notation polonaise suffixée puis les évaluer)
5*(6+2)-12/4
20/(12-2)+(6-4)*5-4/2
(5/8)^2-(6+23)


b) l’algorithme d’évaluation des expressions polonaises suffixées consiste à traiter tous les caractères dans l’ordre de la notation polonaise suffixée jusqu'au dernier. Deux cas sont rencontrés :


-nous traitons un nombre ® il faut l’empiler
- nous traitons un opérateur de calcul ® il faut dépiler deux nombres; effectuer le calcul; empiler le résultat.
La valeur de l’expression calculée est le dernier élément qui se trouve dans la pile.

Exemple : évaluation de l’expression 5 6 2 + * 12 4 / - :

2 4
6 6 8 12 12 3
5 5 5 5 40 40 40 40 37

+ * / -
Pile

Travail Demandé

1- Proposer une structure de données pour stocker une expression mathématique exprimée en notation polonaise suffixée.
2- Écrire un algorithme qui permet d’évaluer une expression représentée avec la structure que tu as proposé dans la question précédente.
3- Traduire votre algorithme en fonction en langage C++, à laquelle l’expression est passée comme paramètre.


Partie II : Traduction d’une expression mathématique en notation polonaise suffixée

Nous supposons qu’il n’y a que les signes ^ * / + - ( )
Avec l’ordre de priorité connu et l’exécution de gauche à droite. Nous empilons une parenthèse ‘(‘ au départ de la pile et nous ajoutons une parenthèse fermente ‘)’ à la fin de l’expression.
Le travail consiste à traiter les caractères dans l’ordre de l’expression mathématique, jusqu’à la fin de l’expression. Quatre cas se présentent
nous traitons un nombre ® il va compléter le résultat
nous traitons une ‘(‘®nous empilons
nous traitons une ‘)’ ®nous dépilons jusqu’à ‘(‘ comprise; les opérateurs dépilés vont compléter le résultat.
Nous traitons un opérateur ®nous dépilons tous les opérateurs plus prioritaires ou de priorité égale, et les ajoutons au résultat. Puis nous empilons l’opérateur traité.




Exemple : traduction de l’expression 5*(6+2)-12/4

Caractère traité 5 * ( 6 + 2 ) - 12 / 4 )
+
( ( ( /
* * * * * - - -
( ( ( ( ( ( ( ( ( ( (
résultat 5 6 2 + * 12 4 / -

Travail Demandé

Proposer une structure de données pour représenter une expression mathématique ordinaire.
Définir la structure de données pile qui va être utilisé par l’algorithme de traduction
Réutiliser la même structure de données de la question 1, partie1 pour stocker le résultat de l’algorithme de traduction.
Écrire l’algorithme de traduction.
Développer une fonction en C++ qui permet à partir d’une expression mathématique ordinaire représentée avec la structure proposée dans la question 1 d’avoir une expression polonaise suffixée.

Partie III :
Dans cette partie, nous essayons de faire la synthèse.
Travail demandé

Écrire un programme en C++ qui permet à l’utilisateur d’introduire une expression mathématique ordinaire, puis il lui offre les chois suivants :
a. vérification si l’expression est correcte ou non (optionnel).

b. Traduction vers la notation polonaise suffixée en faisant appel à la fonction de traduction.
c. Évaluation de l’expression en faisant appel à la fonction d’évaluation.

Travail Supplémentaire (Optionnel)

Faire la même chose mais avec des expressions en notation polonaise préfixée.
Écrire un algorithme qui permet à partir d’une expression polonaise suffixée d’avoir une expression mathématique ordinaire.

Remarques

Il est demandé d’utiliser que des structures de données dynamiques (listes chaînées, piles représentées avec des listes chaînées).
Toute mémoire allouée doit être impérativement libérée enfin de programme.
Ne rien déclarer en global, tout transmettre en paramètre.
Il est recommandé de commencer par la deuxième (2ème) partie.