Série 25 :
Structures de données et templates
Buts
Cette série permettra à ceux d'entre vous qui le souhaitent de vous familiariser avec les templates et les structures de données abtraites.Préliminaires :
Avant de commencer les exercices décrits dans
cette série, créez le répertoire
~/cpp/serie25 et travaillez dans ce
répertoire pour les exercices
ne faisant pas partie du projet.
.
Si vous n'avez pas le temps de faire la partie "exercices" de la série, veillez au moins à en consulter le corrigé.
Exercice 0 : reprise de l'exemple du cours (templates, niveau 0)
Le but de cet exercice est de reprendre les exemples du cours relatifs aux templates (programmation générique).
Cliquez ici si vous souhaitez faire cet exercice.
Exercice 1 : Piles et parenthèses (SDA, niveau 1)
Énoncé
Utilisez les tableaux dynamiques pour implémenter une classe de pile de caractères dans un fichier pile.cc.
Appliquez-la au problème du parenthésage à deux parenthèses vu en cours.
Indications
Essayez d'attaquer le problème tel qu'énoncé ci-dessus sans
lire cette section.
Si par contre vous ne savez pas comment faire, par où commencer, etc..
voici des indications quant à la marche à suivre.
Les indications sont progressives, aussi, dès que vous pensez en savoir assez, essayez de faire l'exercice par vous même.
On veut implémenter une pile. Qu'est-ce qui définit une pile ? Son sommet (le seul élément auquel on peut accéder) et les 4 fonctions : empile, dépile, lecture du sommet et test si la pile est vide.
On vous demande d'implémenter la pile à l'aide de vector. Il vous suffit donc de définir où mettre le sommet : en tête ou en queue du vector ?
Que se passe-t-il quand on empile un nouvelle élément ?
Il devient le nouveau sommet.Si on choisit de représenter le sommet de la pile par la premier élément du vecteur (élément 0) alors quand on empile un nouvel élément il faudra le mettre en 0 et déplacer tout le reste.
Ce qui n'est pas une bonne solution !Par contre si on choisit de représenter le sommet par le dernier élément du vector, empiler consiste alors juste à ajouter un élément au vector.
La pile aura donc comme attribut un vector contenant ses éléments. Le sommet de la pile est le dernier élément du vector.
Avec cette implémentation, empiler un élément revient à l'ajouter au vector, dépiler revient à enlever le dernier élément du vector, lire le sommet revient à lire le dernier élément du vector et tester si la pile est vide à tester si le vector est vide.
- Concernant l'application "test de parenthésage", il suffit de reprendre le code du cours.
Exemple d'application
Entrez une expresssion parenthésée : ([]])
-> Erreur
Entrez une expression parenthésée : ([([()[]])][[()]]())
-> OK
Entrez une expression parenthésée :
Note : Le programme se termine lorsque la chaîne saisie est vide.
Exercice 2 : Piles et parenthèses revisitées (SDA, template, niveau 2)
La pile implémentée dans l'exercice précédent ne peut contenir que des caractères.
Copiez le code du fichier pile.cc dans un nouveau fichier, puis :
- transformez votre classe Pile en modèle de classe paramétré par le type des données à empiler,
- adaptez le restant du code pour faire fonctionner à nouveau le programme comme précédemment.
Pour les "très motivés", question subsidiaire de niveau 3: essayez de produire une variante de ce code dans laquelle la classe Pile n'utilise pas <vector> par composition mais par héritage (i.e. on ne dit plus que Pile a un vector mais qu'elle est un vector).
Exercice 3 : Piles et notation polonaise inverse (SDA, template, niveau 2)
Description
On souhaite ici utiliser le template Pile de l'exercice précédent, pour faire un programme qui interprète les opérations arithmétiques en notation polonaise inverse (c'est-à-dire notation "postfixée").
Cette notation consiste à donner tous les arguments avant l'opération.
Par exemple : 4+3 s'écrit 4 3 +. De même : (4 * 5) + 3 s'écrit 4 5 * 3 +
Notez qu'avec ce système de notation il n'y a pas besoin de parenthèse. Il suffit d'écrire les opérations dans le bon sens.
Par exemple : (4+3)*(3+2) s'écrit 4 3 + 3 2 + * alors que 4 + (3*3) + 2 s'écrit 4 3 3 * + 2 +
Méthode
L'algorithme pour effectuer des opérations données en notation postfixée est le suivant, où P est une pile :
Tant que lire caractère c
Si c est un opérande
empiler c sur P
Sinon
Si c est un opérateur
y <- sommet(P)
dépiler P
x <- sommet(P)
dépiler P
empiler le resultat de "x c y" sur P
À la fin de cet algorithme, le résultat est au sommet de P.
À faire
Dans cette série nous allons simplement nous intéresser aux
opérations sur les chiffres : les seuls opérandes seront les
chiffres de 0 à 9.
(Par exemple : 14+ veut dire 1 + 4 [on
pourra bien entendu aussi noter avec des espaces : 1 4
+])
Reprenez votre template Pile de l'exercice précédent dans une fichier polonaise.cc (les plus à l'aise peuvent bien sûr faire les choses "proprement" en utilisant la compilation séparée plutôt que le "copier-coller").
- Prototypez puis définissez la fonction eval qui prend en
entrée une chaîne de caractères (string) et renvoie un
entier, résultat de l'expression postfixée contenue dans la chaîne.
Cette fonction devra implémenter l'algorithme ci-dessus, et utilisera donc une pile d'entiers.
- Dans la fonction main, lisez une chaîne de caractères
au clavier (correspondant à une opération arithmétique en notation
postfixée) et évaluez-là à l'aide de la fonction précédente, puis
affichez le résultat.
La fonction main bouclera tant que la chaîne entrée n'est pas vide (voir l'exemple ci-dessous).
Indications
- Pour tester sur un caractère (char) c est un
chiffre, faire :
if ((c >= '0') && (c <= '9'))
- Pour convertir un caractère c représentant
un chiffre en
sa valeur
entière (par exemple convertir '3' en 3), faire :
int(c - '0')
Exemple de déroulement
Entrez une expression à évaluer : 8 6 2 - / 3 + -> résultat : 5 Entrez une expression à évaluer : 4 3 + 3 2 + * -> résultat : 35 Entrez une expression à évaluer : 4 3 3 * + 2 + -> résultat : 15 Entrez une expression à évaluer :
Note : Le programme se termine lorsque la chaîne saisie est vide.
Projet : continuation
Cette semaine, vous devez commencer à coder l'étape 4 de l'énoncé.