Correction 25
Structures de données et templates
Exercice 1 : Piles et parenthèses (SDA, niveau 1)
Une variante non-objet de cette exercice existe sous :
Exercice n°39 (page 93 et 274) de l'ouvrage C++ par la pratique.
En suivant la démarche indiquée dans l'exercice, voici un résultat possible :
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
using namespace std;
// un type pour le contenu de la pile pour faciliter d'éventuelles
// modifications.
typedef char Type_el;
// Implémentation simple de la SDA Pile
class Pile {
public:
void empile(Type_el e);
void depile();
Type_el top();
bool est_vide();
// autres fonctions ne faisant pas partie des spécifications
// usuelles des piles
friend ostream& operator<<(ostream&, Pile&);
void vide();
private:
vector<Type_el< data;
};
// fonction pour le controle du parenthesage d'une expression
bool check(string parentheses);
//----------------------------------------------------------------------
int main()
{
string s;
do {
cout << "Entrez une expresssion parenthèsée : " << flush;
getline(cin, s);
if (!s.empty())
cout << " -> " << (check(s) ? "OK" : "Erreur") << endl;
} while (!s.empty());
return 0;
}
void Pile::empile(Type_el e)
{
data.push_back(e);
}
void Pile::depile ()
{
if (!est_vide()) data.pop_back();
}
Type_el Pile::top ()
{
if (!est_vide())
return data[data.size()-1];
else // que faire ?? -> normalement lever une exception
// mais version simplifiée ici
return 0;
//
}
bool Pile::est_vide()
{
return data.empty();
}
void Pile::vide()
{
data.clear();
}
ostream& operator<<(ostream& o, Pile& pile)
{
for (unsigned int i(pile.data.size()-1); i > 0; i--)
cout << "|" << setw(5) << pile.data[i] <<"|" <<endl;
if (!pile.data.empty()) cout << "|" << setw(5) << pile.data[0] << "|" << endl;
cout << "|_____|" << endl;
return o;
}
bool check(string s) {
Pile p;
for (unsigned int i(0); i < s.size(); i++) {
if ((s[i] == '(') || (s[i] == '['))
p.empile(s[i]);
else if (s[i] == ')') {
if ((!p.est_vide()) && (p.top() == '('))
p.depile();
else
return false;
} else if (s[i] == ']') {
if ((!p.est_vide()) && (p.top() == '['))
p.depile();
else
return false;
}
}
return p.est_vide();
}
Avec cette implémentation de la SDA pile, une pile ne peut contenir que des char. Si l'on veut changer le type du contenu de la pile, il est nécessaire de modifier la définition du type Type_el et recompiler.
Exercice 2 : Piles et parenthèses revisitées (SDA, template, niveau 2)
La principale difficulté ici est l'externalisation des définitions des méthodes de la pile, lorsque cette SDA devient un template.
Il est aussi intéressant d'étudier le codage de la surcharge de l'opérateur << (non demandé dans l'exercice).
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
using namespace std;
template
class Pile {
public:
void empile(Type_el e);
void depile();
Type_el top();
bool est_vide();
// autres fonctions ne faisant pas partie des spécifications
// usuelles des piles
template<typename T>friend ostream& operator<<(ostream&, Pile&);
void vide();
private:
vector<Type_el> data;
};
//
bool check(string parentheses);
//----------------------------------------------------------------------
int main()
{
string s;
do {
cout <<"Entrez une expresssion parenthèsée : " << flush;
getline(cin, s);
if (!s.empty())
cout << " -> " << (check(s) ? "OK" : "Erreur") << endl;
} while (!s.empty());
return 0;
}
template<typename Type_el>void Pile<Type_el>::empile(Type_el e)
{
data.push_back(e);
}
template<typename Type_el>void Pile<Type_el>::depile ()
{
if (!est_vide()) data.pop_back();
}
template<typename Type_el>Type_el Pile<Type_el>::top ()
{
if (!est_vide())
return data[data.size()-1];
else // que faire ?? -> normalement lever une exception
// mais version simplifiée ici
return 0;
//
}
template<typename Type_el>bool Pile<Type_el>::est_vide()
{
return data.empty();
}
template<typename Type_el>void Pile<Type_el>::vide()
{
data.clear();
}
template<typename T> ostream& operator<<(ostream& o, Pile<T>& pile)
{
for (unsigned int i(pile.data.size()-1); i > 0; i--)
cout << "|" << setw(5) << pile.data[i] << "|" << endl;
if (!pile.data.empty()) cout << "|" << setw(5) << pile.data[0] << "|" << endl;
cout << "|_____|" << endl;
return o;
}
bool check(string s) {
Pile<char> p;
for (unsigned int i(0); i < s.size(); i++) {
if ((s[i] == '(') || (s[i] == '['))
p.empile(s[i]);
else if (s[i] == ')') {
if ((!p.est_vide()) && (p.top() == '('))
p.depile();
else
return false;
} else if (s[i] == ']') {
if ((!p.est_vide()) && (p.top() == '['))
p.depile();
else
return false;
}
}
return p.est_vide();
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
using namespace std;
template<typename Type_el>
class Pile : private vector<Type_el>{
public:
void empile(Type_el e);
void depile();
Type_el top();
bool est_vide();
// autres méthode ne faisant pas partie des spécifications
// usuelles des piles
template<typename T>friend ostream& operator<<(ostream&, Pile<T>&);
void vide();
};
//
bool check(string parentheses);
//----------------------------------------------------------------------
int main()
{
string s;
do {
cout << "Entrez une expresssion parenthèsée : " << flush;
getline(cin, s);
if (!s.empty())
cout << " -> " << (check(s) ? "OK" : "Erreur") << endl;
} while (!s.empty());
return 0;
}
template<typename Type_el> void Pile<Type_el>::empile(Type_el e)
{
push_back(e);
}
template<typename Type_el> void Pile<Type_el>::depile ()
{
if (!est_vide()) vector<Type_el>::pop_back();
}
template<typename Type_el> Type_el Pile<Type_el>::top ()
{
if (!est_vide())
return (*this)[vector<Type_el>::size()-1];
else // que faire ?? -> normalement lever une exception
// mais version simplifiée ici
return 0;
//
}
template<typename Type_el> bool Pile<Type_el>::est_vide()
{
return vector<Type_el>::empty();
}
template<typename Type_el> void Pile<Type_el>::vide()
{
vector<Type_el>::clear();
}
template<typename T>ostream& operator<<(ostream& o, Pile<T>& p)
{
for (unsigned int i(p.size()-1); i > 0; i--)
cout << "|" << setw(5) << p[i] << "|" << endl;
if (!p.empty()) cout << "|" << setw(5) << p[0] << "|" << endl;
cout << "|_____|" << endl;
return o;
}
bool check(string s) {
Pile<char> p;
for (unsigned int i(0); i < s.size(); i++) {
if ((s[i] == '(') || (s[i] == '[')){
p.empile(s[i]);
cout << p << endl;
}
else if (s[i] == ')') {
if ((!p.est_vide()) && (p.top() == '('))
p.depile();
else
return false;
} else if (s[i] == ']') {
if ((!p.est_vide()) && (p.top() == '['))
p.depile();
else
return false;
}
}
return p.est_vide();
}
Exercice 3 : Piles et notation polonaise inverse (SDA, template, niveau 2)
Une variante non-objet de cet exercice se trouve sous :
Exercice n°41 (page 96 et 281) de l'ouvrage C++ par la pratique.
Voici une solution possible pour cet exercice :
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
using namespace std;
template<typename Type_el>
class Pile {
public:
void empile(Type_el e);
void depile();
Type_el top();
bool est_vide();
// autres fonctions ne faisant pas partie des spécifications
// usuelles des piles
template<typename T>friend ostream& operator<<(ostream&, Pile<T>&);
void vide();
private:
vector<Type_el> data;
};
//
int eval(string entree);
//----------------------------------------------------------------------
int main()
{
string s;
do {
cout << "Entrez une expresssion à évaluer : " << flush;
getline(cin, s);
if (!s.empty())
cout << " -> résultat : " << eval(s) << endl;
} while (!s.empty());
return 0;
}
int eval(string s)
{
Pile<int> p;
// recopie dans la pile
for (unsigned int i(0); i < s.size(); i++)
if ((s[i] >= '0') && (s[i] <= '9')) {
// On a lu un chiffre
p.empile(int(s[i] - '0'));
} else if ((s[i] == '+') || (s[i] == '-') ||
(s[i] == '*') || (s[i] == '/')) {
// recupere le second argument
int y(p.top());
p.depile();
// recupere le premier argument
int x(p.top());
p.depile();
// calcule et empile le resultat
switch(s[i]) {
case '+': p.empile(x + y); break;
case '-': p.empile(x - y); break;
case '*': p.empile(x * y); break;
case '/': p.empile(x / y); break;
}
}
return p.top();
}
template<typename Type_el>void Pile<Type_el>::empile(Type_el e)
{
data.push_back(e);
}
template<typename Type_el>void Pile<Type_el>::depile ()
{
if (!est_vide()) data.pop_back();
}
template<typename Type_el>Type_el Pile<Type_el>::top ()
{
if (!est_vide())
return data[data.size()-1];
else // que faire ?? -> normalement lever une exception
// mais version simplifiée ici
return 0;
//
}
template<typename Type_el>bool Pile<Type_el>::est_vide()
{
return data.empty();
}
template<typename Type_el>void Pile<Type_el>::vide()
{
data.clear();
}
template<typename T> ostream& operator<<(ostream& o, Pile<T>& pile)
{
for (unsigned int i(pile.data.size()-1); i > 0; i--)
cout << "|" << setw(5) << pile.data[i] << "|" << endl;
if (!pile.data.empty()) cout << "|" << setw(5) << pile.data[0] << "|" << endl;
cout << "|_____|" << endl;
return o;
}