Accueil
Professeur et Démonstrateurs
Horaires et locaux
Notes de cours
Démonstrations et devoirs
Examens
Liens utiles
Au sujet du livre de cours
Consultez vos notes
Foire aux questions (FAQ)
|
|
Démonstration 3: Attachez vos tuques (Introduction à C++)
Note: le texte qui précède les exercices (et donc qui suit) provient
d'une planche de démonstration d'une session précédante.
Allocation dynamique en C++
Nous pouvons créer des objets dynamiquement en C++ avec l'opérateur
new
. Un objet existe jusqu'à ce que son opérateur
delete
soit appelé. Pour tout type T, défini par l'usager ou
pas, l'instruction
new T
crée un objet de type T et renvoie un pointeur vers ce dernier.
De même, l'instruction
delete p
détruit l'objet sur lequel pointait p.
Soit la déclaration de classe Stack suivante:
class Stack {
private:
char* elements;
int top;
int size;
public:
Stack(int n); //constructeur
~Stack(); //destructeur
void push(char e);
char pop();
};
l'utilité d'un destructeur est de libérer la mémoire
allouée par le constructeur (ou autre méthode de la classe
). Ceci peut justement se faire grace à delete
Stack::Stack( int n )
{
top = 0;
size = n;
elements = new char[size];
}
Stack::~Stack(){ delete elements; }
main() {
Stack* s = new Stack( 1500 );
//...
delete[] s; //appele le destructeur de s et detruit l'objet
}
Objet statique et dynamique
Contrairement au Java, le C++ permet la création statique et dynamique
d'objet, permettant d'utiliser à notre guise la pile
(stack) ou le monceau (heap). Modifions la déclaration
de classe précédente en rajoutant un constructeur par défaut.
class Stack {
private:
char* elements;
int top;
int size;
public:
Stack(); //constructeur
Stack(int n); //constructeur
~Stack(); //destructeur
void push(char n);
char pop();
};
avec la définition suivante:
Stack::Stack( )
{
top = 0;
elements = new char[1000];
}
Nous pouvons créer un objet Stack des manières suivante:
main() {
Stack s1; //cree un stack de taille 1000
//statiquement (sur la pile)
Stack s2(2000); //cree un stack de taille 2000
//statiquement (sur la pile)
Stack s3 = Stack(3000); //cree un stack de taille 3000
//statiquement (sur la pile)
Stack* s4 = new Stack; //cree un stack de taille 1000
//dynamiquement (sur le monceau)
Stack* s5 = new Stack(); //cree un stack de taille 1000
//dynamiquement (sur le monceau)
Stack* s6 = new Stack( 5000 ); //cree un stack de taille
5000
//dynamiquement (sur le monceau)
s1.push('a');
s2.push('b');
s4->push('c');
(*s5).push('d');
//....
}
Attention: quand s1 est créé sur la pile, le new
qui se trouve dans le constructeur va quand meme allouer la mémoire
pour les données sur le monceau: c'est seulement la mémoire
pour la structure de donnée Stack elle-même qui est allouée
sur la pile.
Comme dit précédemment, un objet obtenu avec new (donc
provenant du monceau) existe jusqu'à ce que leur constructeur soit
appelé, alors que le destructeur d'un objet statique lui, est appelé
AUTOMATIQUEMENT lorsque le nom de l'objet n'est plus en "scope": ce sont
des variables locales
//...
{
Stack s1;
Stack* s2 = new Stack;
} // destructeur de s1 appele, s2 toujours en vie
//....
Note
Dans le tp1, on utilise des Smartpointers et non pas des pointeurs
bruts. Ces Smartpointers sont des objets dont les destructeurs sont appelés
lorsque ces objets ne sont plus en scope, ou lorsque rien ne pointe sur
ces derniers, contrairement aux pointeurs habituels.
Redéfinition d'opérateurs
Une jolie caratéristique de C++ est la redéfinition d'opérateurs.
Ceci est très pour alléger la syntaxe en la rendant plus
concise et rend un programme plus facile à lire. Par exemple, supposons
que nous voulions définir un type rationnel avec les opérations
qui s'y rapportent:
class Rationnel {
private:
int num; denum;
public:
Rationnel( int, int );
Rationnel operator/( Rationnel );
Rationnel operator*( Rationnel );
//....
};
Par exemple, si a et b sont des Rationnels, alors a*b signifie a.operator*(
b ) Après avoir définie les operator/( Rationnel )
et operator*( Rationnel ), on peut facilement manipuler les Rationnels:
void f {
Rationnel a = Rationnel( 1, 2 ); // 1/2
Rationnel b = Rationnel( 1, 4 ); // 1/4
Rationnel c;
c = a*b; // c = 1/8
a = b/c; // a = 2
a = b.operator/( c ); // appel explicite
b = a*b*Rationnel( 1, 3 ) ; // b = 1/24
//....
}
Pratiquement tous les opérateurs peuvent être redéfinis,
à l'exception de l'opérateur de résolution "::", l'opérateur
de membre ".", et l'opérateur de membre par un pointeur ".*",
En règle générale, pour un opérateur binaire
"@", a@b est interprété comme a.operator@(b) ou
encore operator@(a, b) . Pour un opérateur unaire "op", op
a est interprété comme a.operator@() ou encore
operator@(a)
Quelques opérateurs importants que l'on peut rajouter à
la classe Rationnel:
//operateurs binaires
//l'opérateur AFFECTATION, qui retourne
*this
Rationnel& operator=( const Rationnel&
); //copie un objet
// attention a l'auto-copie!
Rationnel& operator+=( Rationnel&
a ); // ajoute
// Rationnel a a
*this
Voici un exemple de classe avec des opérateurs plus exotiques:
class Ptr_to_T {
private:
T* p;
public:
T* operator->(){ return p }; //indirection
T& operator*(){ return *p }; //dereference
T& operator[](int i ){ return p[ i ]
};//subscripting
};
ou encore, en utilisant les templates:
template <class X>
class TableauDynamique
{
X *table;
int nb;
public:
// Constructeur
TableauDynamique() {nb=0;table=NULL;}
// Constructeur de copie
TableauDynamique(const TableauDynamique& td)
{
nb=td.nb;
table=new X[td.nb];
for(int i=0;i<nb;i++)
table[i]=td.table[i];
}
// Opérateur d'affectation
TableauDynamique& operator =(const TableauDynamique&
td)
{
if(this!=&td)
{
delete[] table;
nb=td.nb;
table=new X[td.nb];
for(int i=0;i<nb;i++)
table[i]=td.table[i];
}
return *this;
}
// Destructeur
~TableauDynamique() {delete table;}
// Redefinition de l'operateur d'indexage
X& operator [](int idx)
{
ASSERT(idx>=0);
if(idx>=nb) // le tableau n'est pas assez
grand!
{
X *tmp=new X[idx+1];
for(int i=0;i<nb;i++)
tmp[i]=table[i];
delete[] table;
table=tmp;
nb=idx+1;
}
return table[idx];
}
};
Travail pratique (pas noté mais fortement recommandé)
1) Analyseur lexical
Écrivez en C++ une classe LEX qui offre à son utilisateur un
analyseur lexical capable de reconnaître les tokens suivants dans un
fichier donné:
- INT (ex. de lexème: 12)
- PLUS (lexème: +)
- MOINS (lexème: -)
- MULT (lexème: *)
- DIV (lexème: /)
- POST (lexème: POSTFIX)
- PRE (lexème: PREFIX)
Votre classe doît au minimum fournir à l'utilisateur l'interface suivante:
-
bool next() permet d'analyser le token suivant et
retourne true si un token a été analysé, false sinon
-
string getLexeme() retourne le dernier lexème analysé par next()
-
X getToken() retourne le dernier token analysé par next() , où X sera un type de votre choix (un string ou un int par exemple)
ainsi qu'au moins le constructeur suivant:
-
LEX(string fileName) qui ouvre le fichier ascii fileName en lecture, afin d'y lire les tokens, par des appels à la méthode next() .
Le bout de programme suivant:
string monFichier;
// instanciation de monFichier
Lex lex(monFichier);
while (lex.next())
cout << lex.getToken() << "," << lex.getLexeme() << end;
devrait en principe permettre de découper le fichier monFichier en tokens en les affichant (au format: token,lexeme) ligne par ligne.
Voici ce que ca devrait afficher pour le fichier exemples.post:
POST,POSTFIX
INT,2
INT,3
PLUS,+
INT,4
INT,23
MULT,*
MOINS,-
POST,POSTFIX
INT,2
INT,5
MULT,*
INT,3
PLUS,+
POST,POSTFIX
INT,2
INT,3
PLUS,+
INT,4
PLUS,+
et pour le fichier exemples.pre:
PRE,PREFIX
PLUS,+
INT,2
INT,3
PRE,PREFIX
PLUS,+
INT,2
PLUS,+
INT,3
MULT,*
INT,4
INT,2
PRE,PREFIX
DIV,/
INT,200
PLUS,+
INT,1
INT,1
PRE,PREFIX
PLUS,+
INT,14
INT,23
Note: on suppose dans cet exercice que les lexèmes sont séparés au moins par un espace (ou une tabulation ou un retour charriot).
|
2) Interpreteur d'expressions arithmétiques postfixées
En utilisant la classe LEX de l'exercice précédant,
écrivez un interpréteur capable de calculer des expressions
post-fixées comme celles du fichier exemples.post. On supposera que le mot
POSTFIX est un marqueur de début d'expression.
Note: On ne vous demande pas ici de faire de la vérification de
syntaxe (on suppose que le fichier source à analyser est correctement
formé).
Voici les résultats que devrait afficher votre programme lorsqu'il analyse le fichier exemples.post:
87 // car 2 3 + 4 23 * - -> (4 * 23) - (2 + 3)
13 // car 2 5 * 3 + -> 3 + (2 * 5)
9 // car 2 3 + 4 + -> 4 + (2 + 3)
Idée: nous avons vu en cours qu'une pile permettait d'écrire
facilement un tel interpréteur.
|
3) Interpreteur d'expressions arithmétiques préfixées
En utilisant la classe LEX de l'exercice précédant,
écrivez un interpréteur capable de calculer des expressions pré-fixées
comme celles du fichier exemples.pre. On
supposera que le mot PREFIX est un marqueur de début
d'expression.
Note: On ne vous demande pas ici de faire de la vérification de
syntaxe (on suppose que le fichier source à analyser est correctement
formé).
Voici les résultats que devrait afficher votre programme lorsqu'il
analyse le fichier exemples.pre:
5 // + 2 3 -> (2 + 3)
13 // + 2 + 3 * 4 2 -> (2 + (3 + (4 * 2)))
100 // / 200 + 1 1 -> (200 / (1 + 1))
37 // + 14 23 -> (14 + 23)
Note: on connaît l'arité de chaque opérateur (ici 2).
|
[top] |