TP2 : Calculatrice à Pile

Le but est de fabriquer une calculatrice à pile, telles les HP. On ignorera les problèmes arithmétiques en utilisant le type int et en faisant donc les opérations arithmétiques modulo 2³². Les objets contenus dans la pile peuvent être de type variés. On manipulera ici des entiers ou des listes (d'entiers ou de listes).

1.  Manipulation d'une pile d'entiers

Les types de données sont :

typedef int element_t;
typedef struct pile {
  element_t this;
  struct pile *next;
} *pile_t;

Faire une interface qui permette d'afficher le contenu de la pile, d'ajouter et de supprimer des éléments. On conseille les étapes suivantes :

1. void imprime_element(element_t e);
2. void imprime_pile(pile_t p); qui utilise la fonction ci-dessus.
3. void empile(pile_t *p, element_t e); et void depile(pile_t *p); qui empile ou dépile un élément.
   Vous pouvez aussi décider que la fonction depile donne comme résultat l'objet du haut de la pile, mais alors il faut faire attention au cas où la pile est vide.
4. element_t saisie_element() pour saisir un élément.
5. Testez vos fonctions à l'aide des instructions :

   void read_until_end_of_line()
   {
     int ch;
     while( (ch = getchar()) != EOF && ch != '\n' );
   }
   
   int main ()
   {
     pile_t p = NULL;
     for (;;) {
       char c;
       printf("Commande : (q)uitter, (d)etruire, (a)jouter, (i)mprimer ... ");
       c = getchar(); read_until_end_of_line();
       if (c == 'q') break;
       switch (c) {
         case 'i': imprime_pile(p); break;
         case 'a': empile(&p, saisie_element()); break;
         case 'd': depile(&p); break;
       }
     }
     exit(0);
   }
   

   (corrigé)
6. void copy(pile_t *p, int depth); qui copie le depth-ième élément en première position dans la pile.
7. void delete(pile_t *p, int depth); qui détruit le depth-ième élément.
8. void rotate(pile_t *p, int depth); qui ramène le depth-ième élément en première position dans la pile.
9. Utilisez vos fonctions dans un programme. (corrigé)

2.  Opérations sur les entiers

Ajouter les opérations sur les entiers :

1. Négation du dernier élément de la pile.
2. Addition/soustraction/multiplication des deux derniers éléments de la pile, remplacés par le résultat de l'opération.
3. Division euclidienne, qui calcule quotient et reste.
4. Exponentiation.

3.  Manipulation d'entiers ou de listes

Les types de données sont :

typedef struct pile *liste_t;
typedef int entier_t;
typedef struct element {
  enum type_element { e_entier = 0, e_liste } t;
  union {
    entier_t entier;
    liste_t  liste;
  } v;
} element_t;
typedef struct pile {
  element_t this;
  struct pile *next;
} *pile_t;

1. Modifier le programme précédent pour utiliser des objets explicitement typés comme précisé ci-dessus. On se contente de programmer le minimum pour gérer le type e_liste. (corrigé)
2. Rajouter une commande qui prend les depth-iers objets de la pile et les regroupe en une liste, et une commande qui remplace sur la pile une liste par son contenu. Il faut donc prévoir de quoi afficher et copier les listes. (corrigé)
3. Modifier le programme précédent pour que le type liste_t inclue un compteur de références, afin d'économiser de la mémoire...