Deug MASS 2  Année 2000/2001

U.N.S.A.

ALGORITHMIQUE ET STRUCTURES DE DONNEES

TP N^{o} 10

Piles, Files et Arbres

1 Pile d’entiers

Un pile est une structure de données où les données sont retirées dans l’ordre inverse où elles ont été ajoutées. Le dernier élément ajouté est le premier élément retiré (Last In, First out, LIFO en Anglais).

   Récupérer à l’adresse http://www-sop.inria.fr/lemme/personnel/Guillaume.
Dufay/MASS2/tp10/PileDEntiers.java la classe PileDEntiers qui repré-

sente une pile d’entiers. Compléter les méthodes estVide, estPleine, ajouter et retirer de cette classe qui testent respectivement si la pile est vide, si elle est pleine, qui ajoute un élément dans cette pile et en retire un élément.

Les éléments de la pile sont stockées dans cette classe par un tableau Java nommée contenu. Les éléments y sont rajoutés après les éléments dejà présents. Un entier taille_courante indique le nombre actuel d’élements dans la pile.

2 File d’entiers

Une file est une structure de données où les données sont retirées dans l’ordre où elles ont été ajoutées. Le premier élément ajouté est le premier élément retiré (First In, First out, FIFO en Anglais).

   Récupérer à l’adresse http://www-sop.inria.fr/lemme/personnel/Guillaume.
Dufay/MASS2/tp10/FileDEntiers.java la classe FileDEntiers qui repré-

sente une file d’entiers et compléter les méthodes manquantes.

Comme pour la pile, les éléments de la file sont stockées dans cette classe par un tableau Java nommée contenu. Les éléments y sont rajoutés après les éléments dejà présents, mais en revanche, ils sont retirés à partir du début du tableau (ce qui signifie alors que lorsqu’un élément est retiré, il faut décaler tous les autres dans le tableau).

3 Calculette en Polonaise inversée

On se propose de réaliser une petite calculette en utilisant la classe classe PileDEntiers que vous venez de réaliser.

3.1 Fonctionnement

Les « instructions » données à la calculette sont de deux sortes :

– les chiffres (de ’0’ a ’9’)

– les opérations (’+’, ’-’, ’/’, ’*’)

Cette calculette est de style "Polonaise inversée" (on dit aussi postfixe), les opérations à effectuer sur des chiffres sont indiquées après ceux-ci. Cela signifie par exemple que l’expression 1+5-2 sera codée 15+2-.

Votre calculatrice prendra en entrée l’expression à calculer sous forme postfixée et rendra le résultat de son évaluation. Appel de votre programme : java Calculatrice 15+2-Résultat : 15+2- = 4

Chaque chiffre de l’expression sera mis dans la pile et pour chaque opération il faudra dépiler deux entiers contenus dans la pile, faire le calcul et mettre le résultat dans la pile.

Votre classe Calculatrice contiendra la méthode main ainsi que la mé-

thode public static void calcule(String expression) qui sera appe-

lée par le main.

3.2 Tests

Pour tester votre calculatrice, utilisez ces exemples :

12+2* = 6
15-1+ = -3
62/22++ = 7

3.3 Renforcer le contrôle sur l’expression arithmétique saisie

Si vous n’avez pas fait de contrôle sur l’expression saisie, votre programme ne fonctionnera pas correctement avec les expressions données ci-dessous.

12+*
12+0/
12+:1-

Corriger votre programme pour éviter ces problèmes en affichant un message d’erreur.

4 Les Arbres Binaires

   Récupérer à l’adresse http://www-sop.inria.fr/lemme/personnel/Guillaume.

Dufay/MASS2/tp10/Arbre.java la classe Arbre réprésentant un arbre binaire d’entiers vue en TD 8.

4.1 Affichage du contenu de l’arbre

Afficher de manière récursive l’arbre de trois façons différentes en utilisant les parcours préfixé, postfixé et infixé vus en cours.

Ci-dessosu les prototypes des méthodes à implanter :

void OrdrePrefixe(Arbre racine) {...}
void OrdreInfixe(Arbre racine) {...}
void OrdrePostfixe(Arbre racine) {...}