CHAPITRE 2
auteur: Philippe Moreau (U.P.J.V.)

Exercices de la section 1

Exercice 1:
Utilisation d'une pile, pour le calcul des expressions écrites en "postfixé"
L'expression dite "infixée" s'écrit en "postfixé":
  2  5   +  4  5  3  +  2  ^  *    *
On utilise alors une pile pour pouvoir effectuer les calculs.
Les règles d'utilisation sont alors les suivantes:
Si on rencontre
- un nombre
on l'empile
- une opération
on dépile le sommet et le sous sommet
on effectue le calcul sous-sommet "opération" sommet
on empile le résultat
- une fonction
on dépile le sommet
on calcule la fonction pour la valeur du sommet
on empile le résultat
Avec l'expression ci-dessus donnez les modifications de la pile en respectant les règles (en supposant la pile vide au départ)
 
solution de l'exercice 1.
 
 
Exercice 2: On souhaite écrire une fonction qui calcule la valeur d'une expression écrite en postfixé.
Pour cela, on suppose que cette expression est contenue dans un tableau EXP (chaque case contenant un terme) et qu'une variable N nous indique le nombre de termes de l'expression.
Exemple: pour l'expression de l'exercice 1

Tableau EXP

2  5   +  4  5  3  +  2  ^  *    *

  N
12
On suppose également, qu'il existe les fonctions suivantes:

A l'aide de cette procédure et ces fonctions, écrire une fonction CALC_EXP(EXP,N) (où EXP est le tableau contenant l'expression et N le nombre d'éléments dans l'expression) qui renvoie: Le résultat du calcul de l'expression postfixée (sous forme de chaîne de caractères) (on suppose ici que l'expression est correctement écrite)

solution de l'exercice 2.
 
 
Exercice 3: Que faut-il modifier dans la fonction précédente, si on suppose maintenant que:
CALC_EXP(EXP,N) renvoie:
- Le résultat du calcul de l'expression postfixée si celle-ci est correctement écrite
- 'ERREUR' si l'expression n'est pas correctement écrite
 
solution de l'exercice 3.
 
 
Exercice 4: On désire stocker 2 piles (contenant des entiers positifs) dans un même tableau PILES.
Décrire un schéma permettant ce stockage, en pensant aux manipulations à réaliser sur les piles (il faudra éviter d'avoir à déplacer tous les éléments d'une pile).
 
solution de l'exercice 4.
 
 
Exercice 5: En reprenant le schéma de fonctionnement donné dans la solution de l'exercice précédant, écrire:
- Une fonction EMPILE(PILES,NUMPILE,VAL) qui empile VAL sur la pile NUMPILE et renvoie 'ERREUR' si l'opération n'a pu avoir lieu et 'OK' si tout c'est bien passé.
- Une fonction DEPILE(PILES,NUMPILE,M) qui renvoie -1 si l'opération n'a pu avoir lieu et le sommet de la pile NUMPILE si tout c'est bien passé (où M représente le nombre de cases allouée au tableau PILES).
 
solution de l'exercice 5.
 
 
Exercice 6: En utilisant les fonctions écrites à l'exercice précédant (toujours avec la gestion de 2 piles dans un tableau PILES suivant le schéma de l'exercice 4)
Ecrire les instructions qui permettent de faire passer le sommet de la pile 2 sur la pile1.
 
solution de l'exercice 6.
 
 
Exercice 7: Afin de vérifier le bien fondé de l'utilisation d'une "mémoire circulaire" lors de l'implantation d'une file, on se propose de regarder les manipulations lorsque la file reste cadrée à gauche (dans le tableau). La file peut alors se représenter schématiquement par:

Dans ce cas, l'insertion est identique à l'insertion dans une pile, mais pas la suppression.
Ecrire, dans ce cas, une fonction SUPPRIME_FILE(FILE,ARR) qui supprime un élément (chaîne) dans la file FILE, recadre la file, et renvoie le premier élément ou 'ERREUR' si celui-ci n'existe pas.
(On supposera que les éléments de la file sont des chaînes de caractères)
 
solution de l'exercice 7.
 
 
Exercice 8: Trouver un moyen pour permettre la réalisation de la gestion de 2 files (contenant des entiers positifs) en utilisant une seule structure. (Comme pour l'exercice 4 on cherche, ici, le schéma de principe)
 
solution de l'exercice 8.
 
 
Exercice 9: En reprenant le schéma de fonctionnement donné dans la solution de l'exercice précédant, écrire:
- Une fonction INS_FILE(FILES,NUMFILE,VAL,M) qui insère VAL à l'arrière de la file NUMFILE et renvoie 'ERREUR' si l'opération n'a pu avoir lieu et 'OK' si tout c'est bien passé.
- Une fonction SUP_FILE(FILES,NUMFILE,M) qui renvoie -1 si l'opération n'a pu avoir lieu et le premier élément de la file NUMFILE si tout c'est bien passé.
(où M représente la taille du tableau FILES)
 
solution de l'exercice 9.
 
 
Exercice 10: On reprend le principe de la gestion de 2 files dans un même tableau FILES (comme décrit dans les exercices précédents). On souhaite maintenant simuler le fonctionnement de 2 files d'attentes (par exemple: files d'attente aux caisses d'un supermarché).
Dans ce cas (comportement naturel) l'insertion dans une file ce réalise dans la file qui contient le moins d'éléments. Ecrire:
- Une fonction INS_FILE2(FILES,VAL,M) qui insère VAL à l'arrière de la file la plus courte (le moins d'éléments) et renvoie 'OUVREZ UNE NOUVELLE CAISSE' si l'opération n'a pu avoir lieu et 'OK' si tout c'est bien passé. (On pourra utiliser les fonctions écrites à l'exercice 9)
 
solution de l'exercice 10.

 

Auteur: Philippe Moreau (U.P.J.V.)