TP 4

Le but de ce TP est de manipuler intensivement des listes chaînées, en particulier dans le cas où elles servent à implémenter les piles.

On fabriquera une calculatrice à pile, telles les HP. Une première version fera des opérations sur les réels. L'état de la calculatrice est donc à chaque instant une pile de réels et les opérations s'appliquent aux éléments de cette pile.

Ensuite, la calculatrice sera améliorée pour que les éléments de la pile puissent être des listes (de réels ou de listes...) sur lesquelles on pourra faire des opérations.

Créer un répertoire tdsjava/tp4 pour y mettre tous les fichiers de la séance.

1. manipulation d'une pile de réels

1.1 opérations élémentaires sur une pile

Modifier ce fichier Pile.java en complétant les méthodes push, top, pop et toString. Faire une version récursive et une version itérative de toString.

Une solution (PileSol.java).

1.2 opérations compliquées sur une pile

Les éléments de la pile sont numérotés à partir de 0 (l'élément 0 étant le dernier à avoir été empilé ; le haut de la pile). Définir les méthodes suivantes :

• static Pile delete (Pile p, int n) qui détruit l'élément n.
• static Pile copy (Pile p, int n) qui copie l'élément n en haut de la pile.
• static Pile rotate (Pile p, int n) qui déplace l'élément n en haut de la pile.
• static double get (Pile p, int n) qui donne la valeur de l'élément n.

Une solution (PileExt.java).

2. calculatrice de base

Compléter le fichier (Calculatrice.java) en rajoutant les méthodes suivantes (opérations sur les réels) :

• négation du dernier élément de la pile,
• addition/soustraction/multiplication/division des deux derniers éléments de la pile, remplacés par le résultat de l'opération.

Une solution (CalculatriceSol.java).

3. manipulation de réels ou de listes

Compléter CalculatriceListe.java où le type de données est modifié pour que les éléments de la pile puissent être aussi des listes (chaînées).

Rajouter les opérations :

• une commande join qui prend les n premiers objets de la pile et les regroupe en une liste,
• une commande split qui remplace en haut de la pile une liste par son contenu (l'inverse de la précédente),
• une commande concat qui concatène les deux listes du haut de la pile.

Une solution (CalculatriceListeSol.java).