Test de C++ n° 5 : (19 mai 2001 – durée : 2h)

 © D. Mathieu    mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique
Créé le 06/03/2001 - Dernière mise à jour : 06/03/2001

Tout document autorisé

Sommaire

1 - Question 1
2 - Méthode EditerPrefixe()
3 - Méthode EditerPostfixe()
4 - Méthode EditerInfixe()
5 - Méthode Evaluer()
6 - Constructeur CExpression()

Remarques préliminaires :

Classe CToken

    Une expression est composée de tokens, bien connus. Nous ne considèrerons ici que des expressions arithmétiques formées d'opérandes sous forme de constantes entières non signées et d'opérateurs arithmétiques binaires. Pour effectuer le travail qui vous sera demandé, la classe CToken suivante vous est fournie [1] :
 
namespace nsCompil
{
    class CToken
    {
        friend class CExpression;

        char m_Symbole;
        int  m_Value;

      public :
        CToken (char Symbole);
        CToken (int  Value = 0);

        bool IsOperator (void) const;

        friend std::istream & operator >> (std::istream & is, CToken & Token);
        friend std::ostream & operator << (std::ostream & os,
                                           const CToken & Token);

    }; // CToken

} // nsCompil

    Elle est assez rudimentaire mais permet de lire un token dans un flux d'entrée, de l'afficher dans un flux de sortie, et de connaître sa nature : opérande ou opérateur.

Classe CExpression

   La classe CExpression, dont une partie de la déclaration vous est fournie ci-dessous, permet de gérer une expression arithmétique sous la forme d'un arbre binaire :
 
namespace nsCompil
{
    class CExpression
    {
        typedef nsSdD::CNode2Gen <CToken> CNodeToken;

        CNodeToken * m_Racine;

        // ....

      public :
        CExpression  (std::istream & is = cin);

        ~CExpression (void);

        void EditerPrefixe  (std::ostream & os = std::cout) const;
        void EditerInfixe   (std::ostream & os = std::cout) const;
        void EditerPostfixe (std::ostream & os = std::cout) const;
        int  Evaluer        (void)                          const;

    }; // CExpression

} // nsCompil

    Les identificateurs sont suffisamment explicites. Le constructeur construit l'arbre représentant une expression à partir d'un flux d'entrée tel qu'il est décrit plus haut

    Pour toute la suite, n'envisager que les quatre opérateurs + - * /

Question 1

  Soit le fichier Expr.txt suivant, contenant une expression arithmétique valide en notation polonaise (ordre préfixé) :
 
- + 5 / 2 + 4 3 / * 2 5 6

a) - Quel est l'arbre binaire correspondant à cette expression ?
b) - Quelle est l'expression arithmétique remise sous la forme mathématique classique ?

Corrigé :     Question 1

Sommaire

2 - Méthode EditerPrefixe()

     Ecrire le corps de la méthode publique EditerPrefixe(). Comme cela a été vu dans le TP 14, il faut utiliser localement une méthode privée récursive, que vous appellerez à partir de la méthode publique. Chaque token doit être suivi d'un espace.

Corrigé :      CExpression.h     -     CExpression.hxx      -     CExpression.cxx

Sommaire

3 - Méthode EditerPostfixe()

     Ecrire le corps de la méthode publique EditerPostfixe() selon la même méthode que ci-dessus.

Corrigé :     CExpression.h     -     CExpression.hxx     -  CExpression.cxx

Sommaire

4 - Méthode EditerInfixe()


     Ecrire le corps de la méthode publique EditerInfixe() selon la même méthode que ci-dessus. Pour respecter la valeur de l'expression, le parenthésage peut être nécessaire. Mais il peut être maximal ou minimal. Considérons par exemple l'expression suivante :

    Les algorithmes sont plus ou moins difficiles selon le niveau que vous choisirez. Il faut au minimum que le parenthésage soit juste !

Corrigé :     CExpression.h     -     CExpression.hxx     -  CExpression.cxx

Sommaire

5 - Méthode Evaluer()

     Ecrire le corps de la méthode publique Evaluer() selon la même méthode que ci-dessus. Evaluer une expression signifie calculer sa valeur. On rappelle que cette valeur est :

Corrigé :     CExpression.h     -     CExpression.hxx     -  CExpression.cxx

Sommaire

6 - Constructeur CExpression()

     Ecrire le corps du constructeur. Comme dans le TP 14 et la classe CTree, vous serez obligés d'utiliser une méthode annexe récursive Ajouter(). Chaque fois qu'un opérande est lu dans le flux, l'arbre résultant, qui doit être renvoyé, est une feuille ne contenant que cet opérande. Chaque fois qu'un opérateur est lu dans le flux, l'arbre résultant ne peut être renvoyé que lorsque ses sous-arbres gauche et droit ont été successivement construits.

Corrigé :      CExpression.h     -     CExpression.hxx     -  CExpression.cxx

Sommaire

[1]

A titre documentaire, voir aussi CToken.hxx et CToken.cxx.

© D. Mathieu    mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique