Séries 11 et 12 : Structures de données abstraites/bibliothèques

Buts

Cette série a pour but de vous faire approfondir la pratique de la programmation, en utilisant le thème des structures de données abstraites et l'utilisation des bibliothèques, en particulier les notions de containers et d'itérateurs.

Préliminaires :

Avant de commencer les exercices décrits dans cette série, créez le répertoire ~/Desktop/myfiles/cpp/serie23 et travaillez dans ce répertoire.

Exercice 0 : piles et parenthèses (piles, niveau 0)

Adaptation de l'exercice n°39 (pages 91 et 274) de l'ouvrage C++ par la pratique.
(pages 93 et 274 dans la 2^e édition).

Énoncé

Le but de cet exercice est de vous faire travailler les piles de la bibliothéque standard.

Utilisez des piles pour résoudre le problème du parenthésage à deux parenthèses vu en cours (exemple d'application ci-dessous).

Essayez de le refaire sans regarder la solution dans le 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 1 : piles et notation polonaise inverse (niveau 2)

Exercice n°41 (page 94 et 281) de l'ouvrage C++ par la pratique.
(pages 96 et 281 dans la 2^e édition).

Description

On veut 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 (la valeur de) c sur P
  Sinon
     Si c est un opérateur
        y <- sommet(P)
        dépiler P
        x <- sommet(P)
        dépiler P
        empiler le résultat 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 +])

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 si un caractère (char) c est un chiffre, faire :
```
if ((c >= '0') and (c <= '9'))
```
Pour convertir un caractère c représentant un chiffre en sa valeur entière (par exemple convertir '3' en 3), faire :
```
(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 :

Exercice 2 : Ensembles et itérateurs (niveau 1)

Exercice n°66 (page 171 et 363) de l'ouvrage C++ par la pratique.

Le but est ici de vous faire pratiquer la notion d'itérateur.

Dans un fichier iterator.cc, définisez (en utilisant la bibliothèque standard) un ensemble (set) de caractères contenant 3 éléments (par exemple 'a', 'b' et 'c')

Parcourez cet ensemble à l'aide d'un itérateur pour l'afficher élément par élément.

Définissez une chaîne de caractères (string) et utilisez ensuite l'algorithme de copy (et 2 itérateurs) pour copier le contenu de l'ensemble dans la string.
(Affichez la string pour vérfier).

Si vous voyez ce que je veux dire, terminer en affichant l'ensemble directement à l'écran en utilisant l'algorithme de copy et un ostream_iterator

Exercice 3 : tris (niveau 1)

Exercice n°67 (page 172 et 365) de l'ouvrage C++ par la pratique.

Créez un tableau dynamique d'entiers ou de réels. Remplissez-le avec des valeurs tirées au hasard.

Triez ce tableau en utilisant la bibliothèque standard de C++ et affichez le résultat.

Projet

Pour faire la dernière partie du projet, voir ici.

Pour rendre le projet, voir ici.