| Exercice 0 | Exercice 1 | Exercice 2 | Exercice 3 |
Voici une version avec les piles du standard C++, les stacks :
#include <iostream> #include <stack> #include <string> using namespace std; typedef char type_el; // vérification de parenthèsage bool check(const string& parentheses); //---------------------------------------------------------------------- int main() { string s; do { cout << "Entrez une expresssion parenthèsée : "; getline(cin, s); if (!s.empty()) cout << " -> "; if (check(s)) { cout << "OK"; } else { cout << "Erreur"; } cout << endl; } while (!s.empty()); return 0; } //---------------------------------------------------------------------- bool check(const string& s) { stack<type_el> p; for (auto c : s) { if ((c == '(') or (c == '[')) { p.push(c); } else if (c == ')') { if ((not p.empty()) and (p.top() == '(')) p.pop(); else return false; } else if (c == ']') { if ((not p.empty()) and (p.top() == '[')) p.pop(); else return false; } } return p.empty(); }
Protoype :
int eval(string entree);
ou si l'on veut éviter la copie du passage par valeur, on peut optimiser en :
int eval(const string& entree);
Définition : suivre l'algorithme donné ne devrait pas présenter de difficulté.
#include <iostream> #include <iomanip> #include <stack> #include <string> using namespace std; typedef int type_el; int eval(const string& entree); //---------------------------------------------------------------------- int main() { string s; do { cout << "Entrez une expresssion à évaluer : "; getline(cin, s); if (not s.empty()) cout << " -> résultat : " << eval(s) << endl; } while (not s.empty()); return 0; } //---------------------------------------------------------------------- int eval(const string& s) { stack<type_el> p; // recopie dans la pile for (auto c : s) if ((c >= '0') and (c <= '9')) { // On a lu un chiffre p.push(c - '0'); } else if ((c == '+') or (c == '-') or (c == '*') or (c == '/')) { // recupere le second argument int y(p.top()); p.pop();; // recupere le premier argument int x(p.top()); p.pop();; // calcule et empile le resultat switch(c) { case '+': p.push(x + y); break; case '-': p.push(x - y); break; case '*': p.push(x * y); break; case '/': p.push(x / y); break; } } return p.top(); }
Pour pouvoir créer un ensemble, il faut avant tout utiliser la bibliothèque correspondante. On met donc :
#include <set>
Un ensemble de caractères se déclare simplement ensuite par :
set<char> unensemble;
Pour insérer des éléments, on utilise la méthode insert :
unensemble.insert('a'); unensemble.insert('b'); unensemble.insert('c');
Si l'on souhaite maintenant parcourir cet ensemble, il nous faut
un itérateur pour cette classe "ensemble". Il se déclare par
set<char>::iterator.
Si on veut partir du début de l'ensemble, cela correspond pour
l'itérateur à
la valeur retournée par la méthode begin() de la
classe set (comme tout container de la STL).
On aura donc :
set<char>::iterator i(unensemble.begin())
De même, la valeur (suivant la) finale correspond à unensemble.end(), et pour faire avancer un itérateur
on peut utiliser l'opérateur ++ comme pour les nombres et
pour les pointeurs.
L'accès à la valeur du container désignée par un itérateur, par exemple i, se fait en utilisant l'opérateur * : *i
On aboutit alors à :
cout << "mon ensemble contient :" << endl; for (set<char>::iterator i(unensemble.begin()); i != unensemble.end(); ++i) { cout << " " << *i << endl; }
En C++11, on aurait aussi pu, plus simplement écrire :
cout << "mon ensemble contient :" << endl; for (auto const& e : unensemble) { cout << " " << e << endl; }
mais le but premier de cet exercice est de travailler les itérateurs ;-).
Ensuite, pour copier un container (par exemple set) dans un autre (par exemple string), il est impératif que le second ait
au moins la place pour accueillir la copie, c.-à-d, ait au moins la
taille du container copié.
Dans notre cas on crée donc une string avec au
moins 3 caractères :
string s("abc");
La copie s'effectue alors simplement avec l'algorithme générique de copie :
copy(unensemble.begin(), unensemble.end(), s.begin());
La copie sur la sortie cout se fait de même, sauf qu'il
faut "transformer" le flot cout en un
itérateur ; ce qui se
fait avec [niveau avancé] ostream_iterator<char>(cout, ",
"), où le dernier argument représente le séparateur utilisé entre
chacun des éléments du container affichés.
Voici, pour finir, le code complet :
#include <iostream> // pour cout #include <algorithm> // pour copy #include <set> #include <string> #include <iterator> // pour ostream_iterator using namespace std; int main() { set<char> unensemble; unensemble.insert('a'); unensemble.insert('b'); unensemble.insert('c'); cout << "mon ensemble contient :" << endl; for (set<char>::iterator i(unensemble.begin()); i != unensemble.end(); ++i) { cout << " " << *i << endl; } string s; // pour utiliser copy, il est impératif que la chaîne ait // la place nécessaire, donc ici au moins 3 caractères. // En pratique on utilisera donc pas copy pour CREER un // nouveau container, mais bien pour COPIER des valeurs; s = "xxx"; copy(unensemble.begin(), unensemble.end(), s.begin()); cout << s << endl; // affichage cout << "mon ensemble = "; copy(unensemble.begin(), unensemble.end(), ostream_iterator<char>(cout, ", ")); cout << endl; return 0; }
L'exercice est suffisamment simple, je crois, pour que la solution
se passe de commentaires.
Voici une solution possible :
#include <vector> #include <algorithm> // pour sort() #include <random> #include <functional> // pour bind() #include <iostream> #include <iterator> // pour ostream_iterator using namespace std; // Un tableau de valeurs. typedef int Valeur; typedef vector<Valeur> Tableau; void affiche(Tableau t) { copy(t.begin(), t.end()-1, ostream_iterator<Valeur>(cout, ", ")); cout << t.back() << endl; } int main() { // choix de la graine random_device rd; // utilisé ici pour tirer la graine au hasard unsigned int graine(rd()); // choix du générateur et initialisation (graine) default_random_engine generateur(graine); // distribution uniforme entre -5 et 5 uniform_int_distribution<Valeur> distribution(-5, 5); // pour les tirages auto tirage(bind(distribution, generateur)); // un tableau de, disons 25, valeurs à trier. Tableau tableau(25); for (auto& element : tableau) { element = tirage(); } cout << "avant le tri :" << endl; affiche(tableau); // trie le tableau sort(tableau.begin(), tableau.end()); cout << endl << "après le tri :" << endl; affiche(tableau); return 0; }