TD-5, encore les pointeurs

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/X.97/TD-5/enonce.html

Programmes Prenom.Nom.c à déposer par ftp sur poly en /users/profs/maranget/TD-5.

1 Calculatrice HP

On se propose de réaliser une petite calculette HP.

1.1 Quatre opérations

Cette première partie s'inspire du cours. On utilisera une pile stack, globale et codée en machine par une liste d'entiers, voici la définition de stack et le constructeur des listes :

typedef struct cell {
  int val;
  struct cell *next;
} Cell, *Stack;

Stack stack = NULL;

Cell *cons(int val,Cell *next)
{
  Cell *r;

  r = (Cell *)malloc(sizeof(Cell));
  if ( r == NULL) {
    fprintf(stderr,"Plus de memoire\n");
    exit(-1);
  }
  r->val = val;
  r->next = next;
  return r;
}

Écrire les fonctions de base de manipulation de la pile, affichage de la pile (afficher), empilage (push) et dépilage (pop). Voici des signatures possibles :
```
void afficher(void)
int pop(void)
void push(int i)
```
Une quelconque des quatre opérations (par exemple -) se réalise ainsi : dépiler le second argument (par exemple i₂), dépiler le premier argument, (par exemple i₁), effectuer l'opération (par exemple i₁-i₂) et empiler le résultat.

La calculatrice obéira à un programme contenu dans une chaîne de caractères et affichera, à chaque étape intermédiaire, le caractère lu (utiliser printf avec le format "%c") et l'état de de la pile. Par exemple, pour le programme "12-34++", on aura (la pile est affichée du sommet vers le fond) :
```
    []
1 : [1]
2 : [2, 1]
- : [-1]
3 : [3, -1]
4 : [4, 3, -1]
+ : [7, -1]
+ : [6]
```
Vous aurez donc à lire la chaîne-programme caractère par caractère (rappelez vous qu'une chaîne est un tableau de caractères) et à empiler un entier ou à réaliser une opération selon ce que vous avez lu. Les quatre opérations devront bien entendu utiliser les primitives de pile, push et pop. Attention au sens de la soustraction et de la division.

1.2 Opérations avancées sur les piles

Les vraies calculatrices HP ont des touches spéciales qui permettent des manipulations de la pile. Les opérations suivantes (qui diffèrent un peu de celles des calculatrices HP) sont à réaliser sans allouer aucune cellule de liste.

Échanger les deux éléments du sommet de pile. Cette opération sera réalisée par le caractère 's'. Ainsi, le programme "12s-" donnera le résultat suivant :
```
    []
1 : [1]
2 : [2, 1]
s : [1, 2]
- : [1]
```
Rotation de la pile vers le haut : tous les éléments montent d'un cran vers le sommet de pile, le sommet de pile se retrouve en fond de pile. Le programme "4321u" devra produire :
```
    []
4 : [4]
3 : [3, 4]
2 : [2, 3, 4]
1 : [1, 2, 3, 4]
u : [2, 3, 4, 1]
```
Rotation de la pile vers le bas : c'est l'opération inverse, tous les éléments descendent d'un cran, le fond de pile se retrouve en sommet de pile. Ainsi, le programme "4321d" s'exécute ainsi :
```
    []
4 : [4]
3 : [3, 4]
2 : [2, 3, 4]
1 : [1, 2, 3, 4]
d : [4, 1, 2, 3]
```

Remarquez que les rotations reviennent, pour la rotation vers le haut, à mettre la cellule de tête en queue de liste et pour la rotation vers le bas, à mettre la cellule de queue en tête de liste. Vous aurez sans doute intérêt à faire de petits dessins pour vous guider.

La solution de cet exercice apparaîtra en hp.txt.

2 S'il vous reste du temps

Réaliser une calculatrice PH, dont la structure de contrôle est une file. La file sera réalisée par une liste (voir la fin du cours). Une opération se fera en défilant les deux arguments et en enfilant le résultat. Vous pouvez aller jusqu'à donner une signification claire aux rotations et à les programmer.

Ce document a été traduit de L^AT_EX par H^EV^EA.