Objectifs

• Manipulation de structures de données chainées
• Utilisation de piles

Exercice

Evaluation d' expressions arithmétiques entières positives postfixées dont la syntaxe est définie par la grammaire suivante :

    <expression>::=<chiffre>|<expression><chiffre><op>|<chiffre><expression><op>|
               <expression><expression><op>
    <chiffre>::=0..9
    <op>::=+|-|*|/

Question 1

A partir d' expressions en notation infixe, les transformer en notation postifixée.
Evaluer de manière abstraite, après transformation en notation postfixée,  l'expression suivante : (45-(63/2))*(4+(56/3)).

Question 2

On souhaite écrire une fonction qui évalue une expression arithmétique postfixée.
On suppose que l'expression postfixée est enregistrée dans une liste. Les opérandes et les opérateurs sont représentés par les caractères : '0'..'9' , '+', '-', '*', '/'

• écrire le paquetage générique liste_symbole  défini par le type abstrait :
type Liste
opérations
    estVide : Liste -> Booléen
    vide :  -> Liste
    insererEnQueue : Liste*Symbole ->  Liste -- insertion d'un l'élément en queue de liste
    extraire : Liste -> Liste*Symbole -- l'élément extrait de la liste est l'élément de tête
 

• écrire le paquetage générique pile_symbole défini par le type abstrait :
type Pile
opérations
    estVide : Pile -> Booléen
    vide :  -> Pile
    empiler : Pile*Entier ->  Pile
          depiler : Pile -> Pile
          sommet : Pile -> Entier

Question 3

Ecrire une procédure d'évaluation d'une expression postfixée qui prend une liste de symbole en entrée et calcule la valeur de l'expression.

Question 4

Ecrire un programme capable de lire une expression postfixée dans une liste puis de l'évaluer et d'afficher le résultat.