Modele POO pour un QCM de calcul mental

**Nono Sto** · 02/06/2012, 08h51

Chères amies, chers amis

J'ai un peu de temps et je reprend un vieux projet.

Je travaille sur le codage d'un QCM de calcul mental: cependant je séche sur le modèle OO.

L'objectif est d'obtenir une suite de question de ce type:

8 + 2 = ....,
1/2 = .../4,
...+ 1/2 = 1

Petite récap:

Pour l'instant j'instancie une classe Exercice composé par un pointeur vers un objet probleme, un tableau de quatre réponse possible.

L'objet probleme est constitué de deux opérandes.

Maintenant je ne sais pas comment integrer les objet somme(+,-), et quotient(*,/), je subodore une relation d'heritage.

Pourriez vous m'aider à la concetion du mon modele objet SVP.

Merci

Le code de la classe Probleme et Exercice:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#ifndef ProblemeH
#define ProblemeH
 
#include <ctime>
#include <cmath>
#include <string>
#include <vector>
#include <cstdlib>
#include <iostream>
 
#include "Fraction.h"
 
template <class Type1, class Type2>
class Probleme
 
{
    private:        
        Type1 m_operande_1;
        Type2 m_operande_2;
 
    public :
        Probleme() : 
				m_operande_1(), m_operande_2()
			{
			}
 
        Probleme(const Type1& operande_1, const Type2& operande_2) : 
				m_operande_1(operande_1), m_operande_2(operande_2)
			{
			}
 
		Probleme(Probleme const& probleme) : 
				m_operande_1(probleme.m_operande_1), m_operande_2(probleme.m_operande_2)
			{
			}
 
		virtual ~Probleme()
			{
			}
 
		virtual void Afficher()const                     //défénition et declaration obligatoire des fonctions
			{											 //virtuelle template dans le .hpp
				Probleme<Type1,Type2> temp(*this);
				std::cout<<temp.m_operande_1<<std::endl;
			}
		//virtual void Resultat() const;
};
#endif

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#ifndef ExerciceH
#define ExerciceH
 
#include "Probleme.h"
 
template <class Type1,class Type2>
class Exercice
{
    private :  
		Probleme<Type1, Type2> *m_probleme;
        std::vector<Type1> m_proposition;
        std::vector<Type2> m_solution;
 
		//Probleme<Type1, Type2> const& m_probleme; // passage par reference
 
    public :
		Exercice(Probleme<Type1, Type2> *probleme): m_probleme(probleme), m_proposition(4), m_solution(4)
			{
				m_probleme = new Probleme<Type1, Type2>(*probleme);
			}
 
		/*Exercice(Probleme<Type1, Type2>  probleme): m_probleme (probleme), m_proposition(4), m_solution(4) 
			{
			}// constructeur pour le pasage par reference*/
 
        ~Exercice()
			{
				delete m_probleme;
			}
};
#endif

**koala01** · 02/06/2012, 14h00

Salut,

En fait, il faut faire la distinction entre le problème d'une part et l'expression qui le représente

En effet, X + 1 = 4 est une expression, mais 3 * 6 + 12 / 2 = X est aussi une expression

En outre, une expression de base peut etre composée de deux opérandes (1, 3, x, ) et d' un opérateur (+, - , *, / ), mais une expression peut, aussi, être composée de ... deux expression ( 3 * 6 et 1 2 / 2 ) et d'un opérateur ( + )

L'idéal est donc de représenter une expression sous la forme d'un arbre binaire permettant de scinder l'expression sous une forme proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ou encore de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

En effet, de cette manière tu peux parfaitement faire en sorte que ton programme évalue lui-même l'inconnue ( x ) et qu'il "n'aura qu'à" comparer avec la valeur correspondant à la réponse de l'élève

Pour créer ce genre d'arbre, c'est relativement facile, car on remarque que si tout est expression ( 3 peut etre considéré comme une expression

), les valeurs numériques (3, 6, x ) sont d'office des feuilles de l'arbre et les opérateurs sont d'office des branches (voir, des expressions)

C'est une situation tellement habituelle qu'il existe même un desing pattern qui explique comment la mettre en oeuvre : le DP composite

L'idée est donc de créer une classe de base (Expression), abstraite, qui présente une interface nous permettant de travailler avec les expressions et qui se présenterait sous une forme proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
class Node;
class Expression
{
    friend class Factory;
    public:
        Expression( Node* parent = NULL): parent_(parent){}
        virtual ~Expression();
        virtual int evaluate() const = 0; // permet de calculer
        virtual void print(std::ostream &) const = 0;  // permet d'afficher l'expression
        virtual const Expression * parent() const {return parent_;}
    private:
        Node * parent_;
};

Cette classe sera avantageusement dérivée en deux autres classes qui représenteront les feuilles de l'arbre pour l'une et les branche de l'arbre pour l'autre: les classes Leaf et Node, qui ressembleraient à quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Leaf : public Expression
{
    public:
        Leaf(Node * parent = ):Expression(parent){}
        virtual ~Leaf();
};
class Node : public Expression
{
    public:
        Node(Node* parent = NULL):Expression(parent),
                                left_(NULL), right_(NULL){}
       virtual ~Node()
       {
           delete left_;
           delete right_;
       }
       void setLeft(Expression * newLeft)
       {
            // on ne peut définir l'enfant que s'il n'y a pas encore été défini
            // et si la valeur qu'on veut lui donner est un enfant valide
           assert(! left_);
           assert( newLeft_);
           left_ = newLeft;
       }
 
       void setRight(Expression * newRight)
       {
            // on ne peut définir l'enfant que s'il n'y a pas encore été défini
            // et si la valeur qu'on veut lui donner est un enfant valide
           assert(! right_);
           assert( newRight);
           right_ = newRight;
       }
       /* on peut évaluer ce qui se trouve à gauche d'une part et ce qui
        * se trouve à droit d'autre part :D
        */
      int evaluateLeft() const{return left_->evaluate();}
      int evaluateRight() const{return right_->evaluate();}
    protected:
        Expression * left_;
        Expression * right_;
};

Les feuilles se subdivisent en deux grandes catégories :
Les valeurs "fixes" (4, par exemple) d'un coté et les inconnues de l'autre("x", "y", "truc", "brol",...).

L'évaluation d'une valeur fixe est relativement facile : il suffit de ... renvoyer la valeur en question

(l'affichage est lui aussi assez facile, vu qu'il suffit d'afficher la dite valeur

)

Nous aurions donc une classe "Value" qui hérite de Leaf et qui ressemblerait à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
class Value : public Leaf
{
    public:
        Value(int v, Expression * parent):Leaf(parent),value_(v){}
        virtual ~Value(){}
        virtual int evaluate() const{return value_;}
        virtual void print(std::ostream & oss) const
        { oss << value_ ;}
    private:
        int value_;
};

Pour ce qui est de l'inconnue, par contre, si l'affichage est tout simple (il suffit d'afficher le symbole), l'évaluation sera sans doute beaucoup plus compliquée car elle devra pour ainsi dire évaluer l'ensemble de l'expression complexe pour connaitre sa valeur (je te laisse le soin de réfléchir à l'algorithme

).

Elle se présentera sous une forme proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Unknown : public Leaf
{
    public:
        Unknown(std::string const & symbol, Node * parent = NULL):Leaf(parent),symbol_(symbol){}
        virtual int evaluate() const
        {
            /* à toi de jouer :D */ 
        }
        virtual void print(std::ostream & oss)
        {
            oss << symbol_;
        }
    private:
        std::string symbol_;
};

Il nous reste les différents opérateurs à gérer, et, pour ce faire, nous allons les nommer de manière précise : Add (+), Substract (-), Divide (/), Multiply (*).

En effet, chacun va évaluer différemment le résultat qu'il fournit, sous une forme proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Add : public Node
{
    public:
        Add(Node * parent  = NULL):Node(parent){}
        virtual int evaluate() const
        {
            // on ne peut évaluer le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            return left_->evaluate() + right_->evaluate();
        }
        virtual void print(std::ostream & oss) const
        {
             // on ne peut afficher le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            left_->print(oss);
            oss << " + ";
            right_->print(oss);
        }
};
class Substract : public Node
{
    public:
        Substract(Node * parent  = NULL):Node(parent){}
        virtual int evaluate() const
        {
            // on ne peut évaluer le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            return left_->evaluate() - right_->evaluate();
        }
        virtual void print(std::ostream & oss) const
        {
             // on ne peut afficher le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            left_->print(oss);
            oss << " - ";
            right_->print(oss);
        }
};
class Divide : public Node
{
    public:
        Substract(Node * parent  = NULL):Node(parent){}
        virtual int evaluate() const
        {
            // on ne peut évaluer le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            return left_->evaluate() / right_->evaluate();
        }
        virtual void print(std::ostream & oss) const
        {
             // on ne peut afficher le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            left_->print(oss);
            oss << " : ";
            right_->print(oss);
        }
};
class Multiply: public Node
{
    public:
        Multiply(Node * parent  = NULL):Node(parent){}
        virtual int evaluate() const
        {
            // on ne peut évaluer le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            return left_->evaluate() / right_->evaluate();
        }
        virtual void print(std::ostream & oss) const
        {
             // on ne peut afficher le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            left_->print(oss);
            oss << " * ";
            right_->print(oss);
        }
};

Hein? Quoi? Ah, j'ai oublié l'opérateur Equal (=)

Mais non, je ne l'ai pas oublié... je l'ai simplement "laissé de coté" pour t'en parler à part

Car l'affichage de cet opérateur devra sans doute afficher un "?" pour indiquer à l'élève qu'on attend la réponse (bon, ca, c'est pas bien compliqué

) mais, surtout, parce que la valeur renvoyée par Equal devrait, idéalement, correspondre à la valeur de l'inconnue.

Et comme il n'y aurait aucun plaisir à tout te donner, je vais te laisser réfléchir à l'algorithme qui te permettra d'obtenir ce résultat

Mais bon, Equal ressemblera quand même à quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Equal: public Node
{
    public:
        Multiply():Node(NULL){}
        virtual int evaluate() const
        { 
            // A toi de jouer
        }
        virtual void print(std::ostream & oss) const
        {
             // on ne peut afficher le noeud que si... les deux enfants existent ;)
            assert (left_);
            assert (right_);
            left_->print(oss);
            oss << " = ";
            right_->print(oss);
            oss << " ? "<< std::endl;
        }
};

Avec une telle hiérarchie de classe, une expression est tout à fait capable de s'évaluer elle-même et donc... de fournir une valeur qui correspond à l'inconnue recherchée.

Ta classe exercice pourrait donc se simplifier sous une forme proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Exercice
{
    public=
        template <typename iter>
        Exercice(std::string const & problem, iter begin, iter end )  :possibilities_(begin, end)
        {
             problem_ = factory().parse(problem);
        }
        ~Excercice(){delete problem_;}
        void print(std::ostream & oss) const
        {
            problem_->print(oss);
            for(size_t i = ;i<possibilities_.size(); ++i)
            {
               oss<< i+1<<" : " <<possibilities_[i]<<std::endl;
            }
        }
        bool correction(size_t choice) const
        {
            bool result = (possibilities_[choice-1] == problem_->evaluate();
            if(result)
            {
                // que faire si c'est juste
            }
            else
            {
                // que faire si c'est faux
            }
            return result;
        }
        private:
        Equal * problem_;
        std::vector<int> possibilities_;
};

Tu auras sans doute remarqué la présence dans le code de Factory().parse(problem), ainsi que la ligne friend class Factory; dans la classe Expression...

Le role de la classe (et de sa fonction parse) sera de transformer une chaine de caractères du genre de "3 + 1 = Y" en un expression dont la racine est le symbole "=".

Mais ca, je vais aussi te laisser y réfléchir

(sinon, tu n'apprendra rien

)

L'idée est, en tout état de cause que, une fois que tu as créé une expression, si tu invoque la méthode print en lui passant une un flux de type stringstream, tu devrais récupérer une chaine de caractères correspondant (au ? près) à la chaine que tu aura parsée

**Nono Sto** · 02/06/2012, 14h21

Merci beaucoup, je vais lire cela très attentivement cette après midi

**Nono Sto** · 03/06/2012, 10h23

Aie, aie, aie....

tous cela m'est très compliqué, cependant je commence à dégagé la logique de ton code sauf un point qui me parait très obscur:

dès le premiers bout de code:

la classe node herite d'expression et demandais à la construction de celui ci.je comprend pas,

La classe node qui herite d'expressions serait elle pas une classe branche ?

Je suis perdu

**koala01** · 03/06/2012, 16h13

Envoyé par Nono Sto

Aie, aie, aie....

tous cela m'est très compliqué, cependant je commence à dégagé la logique de ton code sauf un point qui me parait très obscur:

dès le premiers bout de code:

la classe node herite d'expression et demandais à la construction de celui ci.je comprend pas,

La classe node qui herite d'expressions serait elle pas une classe branche ?

Je suis perdu

oui, tout à fait...

En fait, pour tout ce qui est du domaine des arbres et des graphes, on parle plus volontiers de noeud que de branches, mais ce qui importe surtout, c'est de faire la distinction entre un "noeud terminal" (une "feuille") et un noeud "non terminal" (une "branche", ou "un noeud")

Ceci dit, je comprend parfatiement ton interrogation, car mes explications sont en francais et le code fourni est plutot anglophone

**Nono Sto** · 03/06/2012, 20h37

Donc il ya bien deux classe disctincte, une Node, et l'autre on vas dire "noeud non terminal"?

**koala01** · 03/06/2012, 22h03

Envoyé par Nono Sto

Donc il ya bien deux classe disctincte, une Node, et l'autre on vas dire "noeud non terminal"?

Tu as bien deux classes, mais c'est:

Leaf qui représente les noeuds terminaux ou feuilles (les opérandes sont des noeuds terminaux ) et
Node qui représente les noeuds non terminaux ou branches (les différents opérateur sont des noeuds non terminaux )

Evidemment, ces deux classes ont une classe de base commune et sont, toutes les deux, dérivées en fonction des besoins

**Nono Sto** · 02/08/2012, 17h54

Chères amies, chers amis

J'ai un souci avec le Design Pattern Composite, en effet en reprenant le schema du DP composite on aurait:

Componment = Expression
Composite = Node
Leaf = Leaf (serait en fait un noeud avec fils = NULL).

Or si on suit les indication de koala01, ma classe Node qui gere les arbre via des pointeur est utilisé par ma classe expression jusque là sa va mais si je suit le modèles donner plus haut Node doit herité d'Expression on seretrouve avec une classe mére qui utilise la classe fille et cela me semble pas normal alors est ce que j'ai loupé quelque chose deans le schema?

Merci

**ternel** · 03/08/2012, 10h38

Normalement, tu as la classe de base, Node, qui présente l'interface.

Bien sur, il y a une ou plusieurs classes Leaf, qui hérite de Node.
Puis un Composite qui est grosso modo un conteneur de Node* (tableau, liste...)

Composite hérite de Node, et mappe chaque fonction sur l'ensemble de ses fils.

Tes opérateurs sont des Composites, tandis que les opérandes sont de simples Nodes.

Il te resterai, je pense à ajouter une factory qui retourne un Node* en recevant une expression.
La factory peut être récursive:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
factory(expression)=>Expression* :=
selon nombre d'operateurs dans (expression):
    cas 0 : new Constante(expression)
    sinon : choisir un operateur o,
              split(expression, o)=>e1, o, e2,
              new Operation(factory(e1), o, factory(e2))
;

Avec Composite nommé ici Operation, et Node nommé Expression, et Leaf nommée Constante

Invité · 03/08/2012, 10h49

sinon on passe en notation infixe , un vulgaire tableau, et on en parle plus

**Nono Sto** · 03/08/2012, 11h58

Merci beaucoup

Normalement, tu as la classe de base, Node, qui présente l'interface

Qu'est ce que tu entend par interface?

Puis un Composite qui est grosso modo un conteneur de Node* (tableau, liste...)

Composite hérite de Node, et mappe chaque fonction sur l'ensemble de ses fils.

J'ai modifié le code ainsi, j'ai renommé ma Classe noeud en classe Tree, cette classe à pour but de gerer via les pointeur toute l'arborescence.

A partir de là, la classe Node (le composite) et Leaf (feuille) peuvent hérité de Tree, Node etant un noeud avec enfant (branche) Leaf un noeud sans enfant (feuille).

Pense tu que cela colle avec ta description?

pour la classe factory je la laisse de coté pour l'instant, mais cela confirme le plan de koala01,c-à-d une classe qui à pour but principale d'etre un parseur

Thank you

**ternel** · 03/08/2012, 13h22

Le concept d'interface, ou classe de base (puisqu'on est en C++), présente les services "métiers".
Mon Node contiendrai ici des méthodes du genre evaluer().

Cette même architecture sert aussi dans la construction d'interface graphique. Les méthodes d'interfaces sont alors dessiner(), rendreVisible(), mettreAuPremierPlan()…

Si je comprends ton architecture, tu as:
Tree
Node: Tree {list<Tree*> fils}
Leaf: Tree

Pour la factory, oui, c'est le même concept que celui de koala01.

Invité · 03/08/2012, 14h29

factory(expression)=>Expression* :=
selon nombre d'operateurs dans (expression):
cas 0 : new Constante(expression)
sinon : choisir un operateur o,
split(expression, o)=>e1, o, e2,
new Operation(factory(e1), o, factory(e2))
;

que c'est complique.

Expression contient la racine de l'arbre et on en parle plus.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
val expression::eval()
 if node is leaf 
  return node.value
 return Expression(node.firstChild).eval() + expression(node.secondChild).eval()

avec bien sur + qui est a choisir parmi loperateur de node.

PS:

J'ai un souci avec le Design Pattern Composite, en effet en reprenant le schema du DP composite on aurait:

dans l'exemple file par koala auquel tu fais reference je presume, il s'agit pas d'un composite.
Dans le composite componment contient soit un soit une liste de noeuds. Ici, expression ne contient qu'un seul noeud.

PS2: je vois pas trop ce qui motive l'heritage, mais bon, pourquoi pas

**koala01** · 03/08/2012, 16h20

En fait, nous sommes bel et bien dans le cadre d'un DP composite à peine détourné:

La seule différence entre le DP composite et ce que je propose, c'est la présence d'un noeud "parent" dans la classe de base.

Cela n'empêche aucunement d'être, stricto sensu, dans le cadre d'un DP composite

:

Expression représente bel et bien l'interface de toute ce qui peut etre considéré comme étant une expression (c'est à dire soit un noeud terminal, soit un trio composé d'un noeud non terminal et de deux opérandes).

Cela va d'un noeud terminal (Leaf) comme une valeur à un noeud non terminal, composé par un opérateur et deux opérande, chaque opérande pouvant être une expression.

Ce qui semble te chagriner, et cela peut se comprendre, c'est que la classe de base (Expression) utilise en interne un pointeur sur Node pour représenter son parent.

Le fait est qu'il existe réellement une restriciton au type de parent que peut avoir une expression : cela doit, effectivement, etre une expression, mais cela ne peut pas être "n'importe laquelle" : il faut impérativement que ce soit un noeud "non terminal".

il n'y aurait en effet aucun sens à permettre le fait que l'expression parent (celle qui contient l'expression courente) soit un noeud terminal (Leaf) car... un noeud terminal ne peut pas avoir d'enfant, et que si quelque chose ne peut pas avoir d'enfant, il devient difficile de le définir comme état parent de quoi que ce soit

Le fait est que le seul moment où il faut, effectivement, faire la distinction entre les noeud terminaux et les noeuds non terminaux est le moment... de la création de l'expression (et des sous expressions).

Une fois cette étape passée, nous ne manipulerons de toutes manières plus que... des expressions

Il n'y a donc absolument aucun problème à décider que la classe de base manipule en interne un pointeur sur un de ses types dérivés étant donné que cela se limite à un détail d'implémentation : toute l'interface va en effet faire en sorte de gérer ce membre comme s'il s'agissait, tout simplement, d'un pointeur sur Expression, et non d'un pointeur sur Node

Par contre, le fait de préciser qu'il s'agit d'un Node * et non d'une quelconque Expression* permet d'éviter les problèmes qu'il pourrait y avoir à essayer de définir un Leaf * comme étant le parent de quelque chose

Invité · 03/08/2012, 18h58

Ton composite est vachement tordu.

L'idée du composite, c'est :
t'as une feuille, et un noeuds qui contient plusieurs instance de mère. Et tous deux héritent d'une mère.

ici, ta feuille hérite de Expression, ..de fait elle contient un noeud!!!!
Donc déjà multiplicité c'est pas glop.

Après tu fais l'hypothèse que l'Expression prend un parent qui n'est pas une feuille. Mais ca change rien. Puisque de toute façon ta feuille se comporte comme un parent. (elle a dejà son noeud a dispo).

Fin bref, il est assez crapuleux.

Bon comme je critique pas mal, si je devais proposer l'interface ca serait plus

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Expression
{
public:
  Expression(Node* n): _node(n){}
  float eval()const{
    if(_n->isLeaf()){
      return _n->value;
    }
    float op1=Expression(_n->first).eval();
    float op2=Expression(_n->second).eval();
    switch(_n->op){
      case PLUS:
        return op1+op2;
        break;
      case TIMES:
        return op1*op2;
        break;
      case MINUS:
        return op1-op2;
        break;
      case DIV:
        return op1/op2;//I like it
        break;
      default:
        return 0;
    }
  } 
  std::string toString()const;
protected:
  Node * _n;
};
class Node{
  Node* first;
  Node* second;
  float value;
  size_t op;
  bool isLeaf()const{return first==NULL;}
}

Un noeud est un noeud. Pas besoin de faire des trucs smart avec.
pas d'héritage ni fioriture. Juste un grotesque wrapper.

**koala01** · 03/08/2012, 23h52

Envoyé par galerien69

Bon comme je critique pas mal, si je devais proposer l'interface ca serait plus

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Expression
{
public:
  Expression(Node* n): _node(n){}
  float eval()const{
    if(_n->isLeaf()){
      return _n->value;
    }
    float op1=Expression(_n->first).eval();
    float op2=Expression(_n->second).eval();
    switch(_n->op){
      case PLUS:
        return op1+op2;
        break;
      case TIMES:
        return op1*op2;
        break;
      case MINUS:
        return op1-op2;
        break;
      case DIV:
        return op1/op2;//I like it
        break;
      default:
        return 0;
    }
  } 
  std::string toString()const;
protected:
  Node * _n;
};
class Node{
  Node* first;
  Node* second;
  float value;
  size_t op;
  bool isLeaf()const{return first==NULL;}
}

Un noeud est un noeud. Pas besoin de faire des trucs smart avec.
pas d'héritage ni fioriture. Juste un grotesque wrapper.

Ca, c'est le meilleur moyen pour perdre énormément en terme d'évolutivité.

Tu vas utiliser une énumération (enfin, j'espère que ce sera une énumération) pour représenter les différents types d'objets que tu est susceptible de manipuler.

Tu pourras, bien sur, te contenter dans un premier temps de l'addition, de la multiplication, de la soustraction et de la division, mais il faut penser que, par la suite, on peut vouloir ajouter d'autres opérations ( fonctions trigonométrique, racine carrée, exponentielle, factorielle, ou que sais-je

)

Le problème, c'est que de tels ajouts vont violer le sacro-saint OCP (Open/Close Principle : le principe Ouvert / fermé):

Le code que tu écris doit rester autant que possible ouvert à l'évolution (ajout des fonctions citées plus haut) mais fermé au modifications : une fois que tu as quelque chose qui fonctionne, il ne faut pas revenir dessus, au risque de provoquer des régressions.

Or, ton switch / case devra, justement, être modifié si tu décide d'ajouter une de ces fonctions

C'est la raison pour laquelle il faut vraiment que les différents opérateurs puissent être utilisés comme des noeud et présenter une interface publique (la fonction eval() ) virtuelle dont le comportement est propre à chaque opérateur.

ainsi, les noeuds ressembleraient à quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Operator : public Expression  // hé oui, les opérateurs sont des expressions :D
{
    public:
        Operator(Expression * left,Expression  * right):left_(left),right_(right) // hé oui, un opérateur relie deux expressions ;)
        {}
    protected : 
        const Expression * left() const{return left_;}
        const Expression * right() const{return right_;}
    private:
        Expression * left_;
        Expression * right_;
};
class Multiply : public Operator// hé oui, c'est un opérateur:D
{
    public:
        virtual double eval() const // héritée de Expression ;)
        {
            return left()->eval() * right()->eval();
        }
        virtual void print(std::ostream & os) const
        {
            left()->print(os);
            os << " * ";
            right()->print(os);
        }
};

De cette manière, si tu veux rajouter une fonction quelconque (exponentielle, factorielle, sinus, cosinus, racine carrée ou autre), tu pourras le faire sans avoir à revenir sur le code de Multiply, Add, Divide ou encore Minus

Tout ce que tu auras à faire, c'est à ... définir la fonction eval et la fonction print.

A ce moment là, le fameux OCP qui m'est si cher est pleinement respecté

Envoyé par galerien69

Ton composite est vachement tordu.

L'idée du composite, c'est :
t'as une feuille, et un noeuds qui contient plusieurs instance de mère. Et tous deux héritent d'une mère.

Mais c'est ce qu'on a: une valeur est à considérer comme une expression qui ne peut contenir aucun enfant, et le noeud peuvent contenir deux enfants max (bon, je passe sur les opérateur unaires comme exponentielle qui ne contiennent qu'une expression

)

ici, ta feuille hérite de Expression, ..de fait elle contient un noeud!!!!
Donc déjà multiplicité c'est pas glop.

Il arrive régulièrement que l'on place, dans une relation parent -> enfant, une référence vers le parent dans l'enfant.

Tu es alors face à une double relation: 0..* (ici, en fait, 2) dans le sens parent->enfant et une relation 1 dans le sens enfant->parent.

Après tu fais l'hypothèse que l'Expression prend un parent qui n'est pas une feuille. Mais ca change rien. Puisque de toute façon ta feuille se comporte comme un parent. (elle a dejà son noeud a dispo).

Non, elle ne se comporte pas comme un parent... elle dispose d'une référence sur son parent, et permet d'y accéder, ce qui est fondamentalement différent

Cette relation permet, tout simplement, de "remonter d'un niveau" dans l'expression

Bon, on peut discuter à loisir de l'opportunité de fournir cette fonctionnalité pour un composite portant sur les expressions mathématiques, mais elle ne mange pas de pain et pourrait s'avérer utile dans le contexte présenté par Nono Sto.

Enfin, la décision de placer la référence sous la forme d'un pointeur sur Node au lieu de sous la forme d'un pointeur sur Expression n'est pas du tout innocente:

Comme je l'ai expliqué plus haut, seuls les noeuds sont susceptibles d'être des parents.

Si l'on venait à décider de placer la référence sur le parent sous la forme d'un pointeur sur Expression, il faudrait donc s'assurer, avant de définir le parent d'une expression, que le candidat est, effectivement, un noeud et non une feuille et gérer, à l'exécution, le cas où ce n'est pas le cas (suite à une erreur de programmation, par exemple)

En forçant le parent à être un pointeur sur Node (ou toute classe dérivée), je m'assure d'être confronté à une erreur de compilation si, d'aventure, je fais une erreur de programmation en essayant de définir un objet qui n'est pas de type Node comme parent d'une expression.

Tu n'as même pas forcément besoin de savoir quel type de noeud sera effectivement créé, mais, une chose est sure, si tu essayes de définir un pointeur sur Leaf (ou toute classe dérivée de Leaf) comme parent, le compilateur t'insultera violemment

De toutes manières, cette référence sur l'expression parent ne sera qu'un détail d'implémentation, dans le sens où il ne sera déjà accessible que sous la forme d'un pointeur sur Expression (au travers de la fonction parent()

) et ce détail ne doit être connu que... par la classe qui se chargera de parser l'expression écrite pour créer l'arbre logique.

(note au passage que j'aurais très bien pu à ce titre placer le constructeur de toutes les classes en accessibilité protégée et déclarer une amitié entre toutes les classes dérivées de Expression et la classe de parsing

)

Une fois l'étape du parsing passée, nous n'aurons plus qu'à manipuler des pointeurs sur Expression, que l'on veuille aller "vers le bas" ou "vers le haut", et cela nous ira très bien

Fin bref, il est assez crapuleux.

Je ne vois pas du tout en quoi il peut etre crapuleux, dans le sens où il nous permet de prévoir une fonctionnalité qui peut s'avérer utile (bien que violant le principe Xp YAGNI

) et où cette manière de faire nous peut nous éviter bien des problèmes du à des erreurs de programmation

Invité · 04/08/2012, 00h51

Je ne vois pas du tout en quoi il peut etre crapuleux

Il est crapuleux dans le sens ou d'ordinaire tu as
A mother
B leaf et C node
B sans lien avec A, alors que là tu as un lien vers un C.

Mais effectivement, c'est la parenté qui m'a perturbé. Et qui me fait toujours ticker, habitué à descendre vers les fils...
---------
Concernant l'OCP, je trouve que tu nous as quand même pondu une usine à gaz. On fait pas un evaluateur de malade, on fait un vulgaire QCM.

Prevoir des operateurs unaires, c'est se priver de la notation infixe (supposant nos op tous binaires) qui nous permet pourtant de nous passer de noeuds et cie...

Néanmoins ce qu'il faut noter, c'est qu'entre ton approche et la mienne, je fais pas de composite, (isLeaf). Tu décides de donner responsabilité à tes noeuds alors que moi non.

Il faut pas calculer cos(arctan(pi/4)*pi) n'est-ce pas

**koala01** · 04/08/2012, 01h27

Envoyé par galerien69

Il est crapuleux dans le sens ou d'ordinaire tu as
A mother
B leaf et C node
B sans lien avec A, alors que là tu as un lien vers un C.

Mais effectivement, c'est la parenté qui m'a perturbé. Et qui me fait toujours ticker, habitué à descendre vers les fils...

Je ne nie pas que, dans le cas présent, ce n'est peut etre pas forcément utile (je l'ai d'ailleurs signalé à deux reprises dans ma dernière intervention

) mais la capacité de remonter vers le parent, quelle qu'en soit la raison (peut etre pour pouvoir appliquer un visiteur supplémentaire

) est régulièrement appréciable

---------

Concernant l'OCP, je trouve que tu nous as quand même pondu une usine à gaz.

A voir...

Outre le fait que ma proposition respecte OCP, elle présente un avantage bien plus intéressant encore, celle de garder les fonctions les plus simples possibles, sans avoir à s'inquiéter de quoi que ce soit

En effet, si chaque opérateur n'a à s'occuper que de l'opération qu'il permet de représenter, toutes les fonctions eval prendront royalement trois à quatre ligne de code, là où, si tu ne fais pas la distinction, tu te retrouvera au final avec une seule fonction qui devra gérer l'ensemble des cas (et donc XXX fois trois à quatre lignes de code

)

Outre OCP, on peut parler un peu de l'XP avec KISS et autres principes tellement à la mode

On fait pas un evaluateur de malade, on fait un vulgaire QCM.

Prevoir des operateurs unaires, c'est se priver de la notation infixe (supposant nos op tous binaires) qui nous permet pourtant de nous passer de noeuds et cie...

Dans l'idéal, les opérateurs unaires devraient effectivement avoir une classe de base différente des opérateur binaires, mais hériter malgré tout de Expression...

Ceci dit, cela ne me choquerait pas outre mesure de voir la classe Tangeante hériter de Node : elle aurait alors un enfant toujours vide (c'est la raison pour laquelle j'ai placé les accesseurs left et right en accessibilité protégée

)

En outre, la représentation sous forme d'arbre binaire n'a strictement aucune influence ni sur la représentation lors de l'affichage ni sur la représentation attendue lors du parsing...

Si tu regarde le code que j'ai présenté dans ma dernière intervention pour la fonction print de multiply, tu constateras qu'il affiche bel et bien X * Y (ou X est l'expression de gauche et Y celle de droite

), ce qui est strictement la représentation à laquelle est en droit de s'attendre l'étudiant

Néanmoins ce qu'il faut noter, c'est qu'entre ton approche et la mienne, je fais pas de composite, (isLeaf). Tu décides de donner responsabilité à tes noeuds alors que moi non.

Un des pilliers de base de la programmation en générale est la délégation des responsabilités

En travaillant comme je le fais, je met tout en place pour que les responsabilités soient correctement déléguées, et donc pour qu'il soit possible d'évoluer dans toutes les directions, y compris le fait de réutiliser, pourquoi pas, l'évaluateur d'expression pour quelque chose de bien plus complexe qu'un simple QCM

Il faut pas calculer cos(arctan(pi/4)*pi) n'est-ce pas

Heuuu... Et pourquoi pas

Tu pars du principe que Nono Sto est prof dans l'enseignement fondamental et que les quatre opérations de base vont lui suffire.

C'est sans doute vrai, du moins, dans un premier temps

Moi je me force à voir un peu plus loin.

J'ai appris depuis longtemps que l'on ne peut être sur que d'une chose dans la vie : on ne peut être sur de rien !

Appliqué au développement, cela se traduirait par : les besoins évoluent sans cesse

Qui sait si un collègue de collège ou un ami ne trouveras pas l'application de Nono Sto des plus intéressantes, et qu'il ne lui demandera pas de l'adapter à la trigonométrie ou aux calculs complexes

Qui sait si Nono Sto ne décideras pas de donner cours au collège ou à l'université l'année prochaine

Qui sait si Nono Sto n'a pas un chercheur en mathématique parmi ses copains qui serait intéressé par le fait de pouvoir analyser des équations complexes

Même si l'évolution des besoins n'est pas certaine il est bien plus intéressant de prévoir les capacités d'évolution, d'autant plus que cela ne mange pas de pain

:

Si tu limites sciemment les possibilités d'évolutions pour quelque chose qui te semble "tellement simple" que tu crois pouvoir battre en brèche les principes fondamentaux de la conception, tu te prépares un avenir bien sombre où tu devras casser tout ce que tu as fait si, pour ton malheur, le besoin d'évolution que tu avais jugé improbable ou très limité vient à se présenter

**Nono Sto** · 04/08/2012, 04h45

Cheres amies chers amis

Voici un debut de brouillon:
pour des raison de facilitation des test j'ai mis le main en friend cependant cela sera corrigé bien sur:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "Tree.h"
#include "Leaf.h"
#include "Add.h"
 
using namespace std;
 
void main()
{
	srand((unsigned)time(NULL));
 
	double *test;
 
	Tree *tree;
	tree = new Tree;
 
	Node Test_3(tree);
}

Tree.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#ifndef TreeH
#define TreeH
 
#include <ctime>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <iostream>
#include <iomanip>
 
class Tree
{	
	protected :
		Tree * pere_haut;
		Tree * pere_bas;
		Tree * fils_haut;
		Tree * fils_bas;
		double* valeurs;
 
	public :
		Tree(): valeurs ( NULL ), fils_haut ( NULL ),
				fils_bas ( NULL ), pere_haut ( NULL ), pere_bas ( NULL ){};
 
		Tree ( const Tree &n) : pere_haut (n. pere_haut ), pere_bas (n. pere_bas ),
				valeurs (n. valeurs ), fils_haut (n. fils_haut ),
				fils_bas (n. fils_bas){};
 
		~Tree () { delete [] valeurs ;};
 
		Tree * cree_fils () {
				Tree * nouveau =new Tree ;
				if ( fils_haut == NULL ) {
								nouveau -> pere_bas = this ;
								nouveau -> pere_haut = frere_haut ();
								if ( frere_haut ()!= NULL )
										nouveau -> pere_haut -> fils_bas = nouveau ;
										fils_haut = nouveau ;
										 }
				else {
								nouveau -> pere_haut = this ;
								nouveau -> pere_bas = frere_bas ();
								if ( frere_bas ()!= NULL )
										nouveau -> pere_bas -> fils_haut = nouveau ;
										fils_bas = nouveau ;
					 }
		 return nouveau ;
};
 
	Tree * frere_haut ()
			{ return ( pere_haut == NULL ) ? NULL : pere_haut -> fils_haut;};
 
	Tree * frere_bas ()
			{return ( pere_bas == NULL ) ? NULL : pere_bas -> fils_bas;};
 
	void set_valeurs ( double *T) {
			if ( valeurs != NULL ) delete valeurs ;
			valeurs = new double;
			valeurs =T;}
 
	double & operator []( int i) { return valeurs [i];}
 
	Tree* creer_arbre(int n);
	void cree_generation (Tree *Tree);
 
	friend void main();
	friend class Expression;
	friend class Node;
	friend class Add;
	friend class Leaf;
 
};
#endif

Tree.cpp

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include "Tree.h"
 
void Tree::cree_generation(Tree *n_Tree) 
{
	Tree *pt;
	Tree *pt_sauv = NULL;
 
	for (pt = n_Tree; pt != NULL; pt = pt->frere_bas())
		{
			if ( pt_sauv == NULL)
			   {
					pt ->fils_haut = pt->cree_fils();
			   }
			else 
				{
					pt ->fils_haut = pt->frere_haut()->fils_bas;
					pt->fils_haut->pere_bas = pt;
				}
			pt->fils_bas = pt->cree_fils();
			pt_sauv = pt->fils_bas ;
		} ;
}
 
Tree* Tree::creer_arbre (int n) 
{
	int i ;
	Tree *pt;
	Tree *arbre;
	arbre = new Tree;
 
	pt = arbre;
 
	for ( i = 0 ; i < n ; i++) 
	{	
		arbre->cree_generation(pt);
		pt = pt->fils_haut;
	};
 
	return (arbre);
}

Expression.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#ifndef ExpressionH
#define ExpressionH
 
#include <sstream>
#include "Tree.h"
 
class Expression
{
	friend class Factory;
	friend void main();
	protected:
	Tree *m_parent;
 
	public:
		Expression(): m_parent(new Tree)
				  {	
				  }
 
		Expression(Tree *const parent): m_parent(parent)
				  {	
				  }
 
		 //int evaluate() const = 0; 
 
		 virtual ~Expression()
				  {
						delete m_parent;
				  }
 
};
#endif

Node.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "Expression.h"
 
class Node : public Expression
{
	protected:
	//Tree *parent;
 
    public:
		Node(Tree *const Parent): Expression(Parent)
			{
				Parent->cree_generation (Parent);
			}
        virtual ~Node()
			{
 
			}
 
		double evaluateUp() const{return *m_parent->fils_haut->valeurs;}
		double evaluateDown() const{return  *m_parent->fils_bas->valeurs;}
};

En reprenant le schema DP composite:

Interface qui gere l'arborescence par pointeur: Tree
Componment = Expression
Composite = Node
Leaf = Leaf (serait en fait un noeud avec fils = NULL).

J'ai mis de coté l'idée de Koala01 à propos de la classe fille appellé par la classe mére, j'ai beaucoup de mal dessus

Voila ce que cela produit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
                                      pere_haut = NULL                  pere_bas= NULL
                                            \                              /
                                              \                          /
                                                         m_parent
                                                 /                           \
                                                /                              \
                                        fils_haut                                   fils_bas 
                                  /                \                      /                \
                                 /                   \                  /                   \
                      fils_haut=NULL     fils_bas =NULL            fils_haut=NULL     fils_bas=NULL

Toute les valeurs sont NULL je me suis pas encore attaqué à initialisation.

Une autre ilustration en image avec les espion:
http://dk1.ti1ca.com/get/81.249.49.2...scence_Exo.JPG

A noter que c'est arbre peut etre recombinant.

Alors qu'en pensez vous suis je sur la bonne voie, pourriez vous me donner des indications à partir de ce code pour m'aider à rectifier.

Merci

Invité · 04/08/2012, 09h11

En outre, la représentation sous forme d'arbre binaire n'a strictement aucune influence ni sur la représentation lors de l'affichage ni sur la représentation attendue lors du parsing...

Fort heureusement que la notation prefixee est la même qu'infixe (me suis trompé dans les posts plus hauts avait ecrit infixe

). Je parle bien de la polonaise du type +*534=17

Ce que je veux dire c'est qu'on peut même se passer de tout le tatouin des noeuds. Et avoir un vulgaire vector (evt. deux).

Si tu regarde le code que j'ai présenté dans ma dernière intervention pour la fonction print de multiply, tu constateras qu'il affiche bel et bien X * Y (ou X est l'expression de gauche et Y celle de droite ), ce qui est strictement la représentation à laquelle est en droit de s'attendre l'étudiant

ouioui j'en doute pas. J'ai déjà également vu ce type d'implem, et j'ai également déjà fait ce type d'implem...
Ce que je retiens, c'est que conceptuellement c'est facile. Ecrire la grammaire pour parser c'est bcp bcp bcp plus délicat (incluant priorité des opérateurs...

). Je parle bien des n-aires opérateurs. La complexité que tu introduis en les traitant est notable. Après si tu me dis que tu fais ca sans trop suer, alors je reviendrai avec plaisir sur ce que je dis

(A supposer qu'il y ait besoin d'un parsing dans le cas ici, ce qui n'est pas sûr)

C'est sans doute vrai, du moins, dans un premier temps
Moi je me force à voir un peu plus loin.

Egalement, mais pas ici. S'il y a un changement à faire, je defonce mes deux classes, ya rien a faire, noeud a 0 responsabilités, seul eval qui est une vulgaire recursive est à revoir.
Donc oui je viole l'OCP.
et oui je préfère un bon KISS.

Modele POO pour un QCM de calcul mental

Langage C++

Discussions similaires

Partager

Partager