Informatique et recherche
opérationnelle
IFT2030

Concepts des langages de programmation

Automne 2002


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]


Dernière mise à jour : Mon Sep 23 10:57:15 EDT 2002
dift2030@iro.umontreal.ca