Optimisation / parser mathématique

**jobherzt** · 31/01/2007, 19h53

Bien le bonjour,

je developpe un logiciel auquel j'aurais besoin d'ajouter un parser mathematique. j'ai commencé a bidouiller un peu flex/bison (c'est assez impressionant d'ailleurs !! ) et je devrais arriver a m'en sortir. je me pose une question neanmoins :

je vais donc parser mn expression, et construire a partir d'elle un arbre qui me permettra ensuite d'evaluer la formule e donnant des valeurs aux variables. pour cela je vais donc creer une classe mere qui sera le type de base de l'arbre, et des classes filles pour chaque "genre" : variable, fonction, operateur binaire, operateur unaire, etc... et c'est la que je m'interroge : vaut il mieux creer UNE classe pour chacun de ses genres, et gerer a l'interieur avec des switch ou des ifs, genre :

Code :

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

1
2
3
4
5
6
7
8
9
 
class nodeOperator : derive de node
.....
 
fonction eval()
switch operateur
case "+" renvoie filsGauche->eval() + filsDroit->eval()
case "*" renvoie filsGauche->eval() * filsDroit->eval()
etc..

ou creer une classe fille pour CHAQUE operateur ou fonction ce qui est un peu plus long mais evite d'avoir des series de tests conditionnels ?

merci..

accessoirement, y a t il des choses auquelles il faut faire gaffe et auquelle je risque de ne pas penser ?? si ca peut m'eviter des erreurs au depart :-)

**Mat.M** · 31/01/2007, 21h51

et c'est la que je m'interroge : vaut il mieux creer UNE classe pour chacun de ses genres, et gerer a l'interieur avec des switch ou des ifs, genre :

Ben je crois que le mieux c'est de créer une classe paramêtrable c.a.d avec template...
( sur codeproject.com je crois qu'il y a un exemple comme cela )
sinon tu peux prendre les conteneurs de la STL et empiler les genres...
Non ? Meilleure idée ?

**jobherzt** · 31/01/2007, 21h59

je ne suis pas sur de te suivre. quand je parlais de genre, je ne voulais pas parler de type au sens entier, double.. mais bien d'element dont le role est different (operateur, variable, valeur numerique..), et dont le traitement vont etre different ! je ne vois pas trop comment je pourrais me depatouiller avec des templates... si tu povais m'en dire un peu plus ! merci :-)

**HanLee** · 01/02/2007, 03h50

Tu as regardé du côté de boost::spirit ?

Et si tu voulais tout coder toi-même, comme en général une expression est un type récursif, et en même temps une somme disjointe de plusieurs types, soit tu peux essayer boost::variant, qui permet d'en faire.

La méthode polymorphisme avec héritage, j'aime pas trop, il faut que tu utilises des visiteurs pour pouvoir ajouter simplement des fonctions, sinon tu serais obligé de modifier le code de chaque classe, ce qui est assez lourd.

Ca revient au même que boost::variant, mais plus long.

**jobherzt** · 01/02/2007, 12h55

si je ne m'abuse, boost::spirit est un analyseur lexical/syntaxique, et comme je le disais je n'ai (pour l'instant

) pas trop de probleme de ce coté la, en utilisant bison et flex..

pour ce qui est du polymorphisme, je suis bien obligé dans la mesure ou chaque "genre" de noeud va necessiter un traitement different, donc un boost::variant ne suffira pas.. enfin je crois

il faut bien comprendre que l'expression mathématique n'est pas evaluée au moment du parsing (c'est comme ca qu'on dit ?) mais doit etre stockée (a priori sous forme d'arbre)...

**Charlemagne** · 01/02/2007, 18h08

Envoyé par jobherzt

je ne suis pas sur de te suivre. quand je parlais de genre, je ne voulais pas parler de type au sens entier, double.. mais bien d'element dont le role est different (operateur, variable, valeur numerique..), et dont le traitement vont etre different ! je ne vois pas trop comment je pourrais me depatouiller avec des templates... si tu povais m'en dire un peu plus ! merci :-)

Je crois qu'à ta place j'utiliserais des fonctions virtuelles. Ca t'éviterais de faire des switchs, qu'il te faudrait remettre à jour à chaque nouvelle classe.
Ex:

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
 
class expr
{
  ...
  virtual expr *eval() =0;
  virtual expr *plus() =0;
};
 
typedef auto_pointer<expr> Expr;
 
template<class T>
class value : public expr
{
  T val;
  ...
  virtual expr *operator() { return new value(val); }
  virtual expr *plus(expr *b) { return new value(val+b->val); }
};
 
class binop: public expr
{
  Expr a,b;
  ...
};
 
class plusop : public binop
{
  virtual expr *eval() { return a->eval()->plus(b->eval()); }
};

**jobherzt** · 01/02/2007, 18h27

Envoyé par Charlemagne

Ca t'éviterais de faire des switchs, qu'il te faudrait remettre à jour à chaque nouvelle classe.

pourquoi est ce que je devrais remettre a jour mes switch a chaque nouvelle classe ? l'ajout d'une classe n'a pas de raison d'avoir d'effet sur les autres.... je te montre le debut de ce que j'ai fait (c'est encore une sorte de "brouillon" avant d'attaquer vraiment). je n'ai pas besoin de template a priori, mes constantes numeriques seront toujours du meme type "REEL". ma question serait plutot de savoir si dans le cas ou j'aurais vraiment beaucoup (mais genre vraiment :-) ) a evaluer mon expression avec different parametetre, le fait d'avoir a effectuer un switch a chaque fois que j'ai une operation "coute" plus en temps de calcul que d'avoir une classe "dédié" pour chaque operateur ou fonction ! (je ne suis pas clair, hein

)

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
 
#include "pave.h"
 
class node
{
	protected:
		interval value;
 
	public:
 
		node()
		{
		}
		virtual interval eval(const pave& parameters,const REEL& variable) {}
		//virtual void contract(pave& parameters, const REEL& variable ) const =0;
};
 
class nodeBinaryOp : public node
{
	protected:
		char op;
		node * nR;
		node * nL;
	public:
		nodeBinaryOp(char _op, node * _nL, node * _nR)
		{
			op=_op;
			nL=_nL;
			nR=_nR;
		}
 
		interval eval(const pave& parameters,const REEL& variable)
		{
			switch(op)
			{
				case '+' : value = nL->eval(parameters, variable) + nR->eval(parameters, variable); break;
				case '*' : value = nL->eval(parameters, variable) * nR->eval(parameters, variable);break;
				case '-' : value = nL->eval(parameters, variable) - nR->eval(parameters, variable);break;
				case '/' : value = nL->eval(parameters, variable) / nR->eval(parameters, variable);break;
			}
 
			return value;
		}
};
 
class nodeConstant : public node
{
	public:
	nodeConstant(interval _val)
	{
		value=_val;
	}
	interval eval(const pave& parameters,const REEL& variable)
	{
		return value;
	}
};

**Charlemagne** · 01/02/2007, 19h20

A priori tu veux faire une "calculatrice".
Si c'est le cas, ça simplifie la programmation par rapport à concevoir un "Mathématica".
Et tu n'auras probablement qu'un seul switch pour ta fonction d'évaluation. Mais si tu comptes rajouter plus de fonctionnalités, t'auras toujours plus de switchs, qu'il te faudra remettre à jour à chaque nouvelle classe (nombres complexes, variables, fonctions scientifiques, ...).

Je conseillerais plutôt de faire des classes dédiées, plutôt que de regrouper les 4 opérations binaires.
Mais regroupe les dans une classe de base commune, pour factoriser le code.

Et puis, je m'arrangerais pour que la fonction d'évaluation ne reçoive aucun paramètre (je vois pas bien à quoi correspond ton "pave").
Mais une classe "variable" pourrait très bien retrouver la valeur associée à partir d'un nom.
par exemple du genre:

Code :

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

1
2
3
4
5
6
7
8
class variable : public expr
{
  static map<string,expr*> vars;
 
  map<string,expr*>::iterator it;
  variable (const string &s) : expr() { it=vars.insert(s).first; }
  virtual expr *eval() { return *it; }
};

**HanLee** · 01/02/2007, 19h46

boost::variant peut aussi très bien convenir.

Regarde comment c'est fait ici :

http://www.boost.org/doc/html/varian...ursive-wrapper

Tu n'es pas obligé d'utiliser la même conception présentée. Moi personnellement à la place de mettre binary_op sous forme de classe template, je rajouterais un autre paramètre à son constructeur de type boost::function<float (float, float)> par exemple qui me permettrait de construire des nouvelles fonctions dynamiquement, de manière simple, au lieu de rajouter à chaque fois des nouveaux types dans la définition.

**jobherzt** · 02/02/2007, 20h20

Bon, c'est vrai que je n'ai pas donné beaucoup de détail

En fait ce que je fais ne ressemble vraiment pas a une calculatrice.. meme si ca n'est pas un mathrmatica, c'est quand meme un chouille compliqué. La difference principale est que dans une calculatrice une expression (contenant eventellement des variables qui ont été prédefinies dans ce cas) est évalué au moment ou elle est parsé. Dans cette situation, on verifie la puissance de lex/yacc, puisque ca se fait (y compris avec une gestion simplifiée de variable) en quelques minutes (lttéralement !!) et sans avoir a construire d'arbre.

en 2 mots, il ne s'agit pas d'un systeme qui me permettrait de faire :

Code :

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

1
2
3
4
5
 
>x=2
2
>x+3
5

d'ailleurs mon programme ne sera pas interactif...

Dans mon cas au contraire, lorsque je parse mon expression, je ne dois pas l'évaluer mais la stocker (donc dans un arbre) pour pouvoir la manipuler et l'utiliser ensuite. c'est pour ca que j'ai besoin d'une structure "explicite" d'abre, c'est aussi pour ca que ma fonction d'evaluation prend des parametres. c'est pour ca enfin que je n'aurais pas besoin d'un systeme complexe de gestion de variables, je n'aurais qu'a fournir a ma fonction d'evaluation une liste de valeur. pour info, il s'agit d'un logiciel de modelisation/optimisation.

par ailleurs, ne confondons pas les "types" (entier, float, complexe..) et ce que j'ai appellé les "genres" a defaut d'un mot plus approprié (valeur numerique, operateur (+,-..) fonction (sin, exp..)).

c'est pour ca que je n'ai pas tellement d'autre solution que d'utiliser le polymorphisme, vu que je fais coexister des "genres" différents dans un meme arbre, et cela ne se regle pas a coup de template ou de boost::variant vu que chaque genre necessite une structure de classe bien specifique... (les operateurs binaires ont 2 "fils" alors que sin et cos n'en ont qu'un, par exemple..)

Si j'avais besoin d'utiliser plusieurs types (mais ca n'est pas le cas), je pourrais sans doute gérér ca avec des templates. mais je n'aurais pas a modifier mes "switch".

si je veux rajouter un genre ou un element d'un genre, au pire ca me fera creer une nouvelle classe heritant de "node" ou rajouter une ligne dans un switch, mais rien de plus..

ceci étant posé, ma question ne concernait donc que la vitesse relative de 2 systemes, a savoir :

- exploiter a fond le polymorphisme et utiliser une classe pour plus, une classe pour moins, etc.
- n'utiliser le polymorphisme que pour distinguer les differents genre, puis "switcher" a l'interieur de chaque classe. (une classe pour les operateurs binaires, puis un switch pour savoir s'il s'agit d'un plus ou d'un moins..) plus simple a ecrire, mais peut etre plus lent ??

voila, j'espere que c'est plus clair :-) et sinon, ne vous cassez pas la tete, je verrais bien a l'usage !!

**HanLee** · 03/02/2007, 05h14

Selon ta solution, bah, moi je penserais que plus de types possibles serait plus rapide, mais j'en sais trop rien. Fais des tests !
Faire un switch revient à faire du polymorphisme à la main, qui est sera peut-être moins efficace que celui implémenté avec la table des fonctions virtuelles.

<Digression>
Et sinon, les genres dont tu parles, ce sont bien des types, mais récursifs. On ne les évalue pas, ils forment des noeuds de l'expression sous forme arborescente.
Ce sont des sous-types d'une expression, qui peut se représenter par cette définition :

Code :

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

1
2
3
4
EXPRESSION =
   Réel
|  Expression_unaire : (Réel -> Réel) * EXPRESSION 
|  Expression_binaire : (Réel * Réel -> Réel) * EXPRESSION * EXPRESSION

Où le caractère '*' désigne le produit cartésien. Avec ça tu peux construire la majorité des expressions analytiques usuelles.

Donc je pense que ton but est de faire une arborescence qui à l'expression sin(3 + cos(4)) associe :

Expression_unaire(sin, Expression_binaire(+, 3, Expression_unaire(cos, 4)))

</Digression>

------

Et sinon, je ne sais pas pourquoi tu dis que la méthode avec boost::variant ne permet pas de faire ce que tu fais pour l'instant. Je sais pas si tu as lu ce que je t'ai montré :/.

En tout cas je te passe en pièce jointe un code en exemple qui compile que j'viens de faire, dis moi si c'est équivalent à ce que tu as déjà fait.

**jobherzt** · 03/02/2007, 11h14

oui, ok ! ce que je voulais c'etais smplement distinguer les 2.. c'est por ca que e les ai appelés genre :-)

sinon, pour boost variant, j'avais essayé de regarder un peu.. je connais mal, donc je me trompe peut etre, mais je ne suis ps sur que ca corresponde a ce que je veux. en effet, je ne vais pas avoir seulement a l'evaluer, mais aussi a faire des manipulations plus complexe, a parcourir l'arbre dans tous les sens... donc chacun de mes "types/genre/classe fille" va avoir des metodes assez particuliere... mais j'avoue que c'est assez impressionnant, je me demande si je ne pourrais pas essayer un mixage entre ca et ce que j'ai :-) a essayer..

**jobherzt** · 03/02/2007, 17h44

meme si finalement je n'utiliserais pas boost::variant, ton exemple m'a mis sur la bonne piste :-) utiliser un pointeur de fonction !! petit exemple :

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
 
class nodeUnaryFunc : public node
{
	protected:
		node * nB;
		interval (*ptrEvalFunc)(interval);
	public:
		nodeUnaryFunc(node * _nB, string funcName)
		{
			nB=_nB;
			if(funcName == "exp")
			{
				ptrEvalFunc=&iExp;
			}
                        //d'autre fonctions à venir....
		}
 
		interval eval(const pave& parameters,const REEL& variable)
		{
			return (*ptrEvalFunc)(nB->eval(parameters, variable));
		}
};

ainsi, j'aurais toujours une serie de test, mais seulement dans le constructeur, donc ca sera fait une fois pour toute.. je pense que ca tient la route, qu'en pensez vous ??

**HanLee** · 03/02/2007, 20h06

J'aime pas l'idée de faire ça dans le constructeur.

Ton noeud nodeUnaryFunc n'est pas un objet dans le sens POO classique, où ya un utilisateur et tout ça. C'est censé représenter un objet mathématique tout ce qu'il y a de plus simple : une fonction unaire, et une expression en tant qu'argument.
Moi je préfère un constructeur qui contient un ptr de fonction et un pointeur vers une expression, et à l'appel du constructeur, tu utiliserais une fonction qui convertit les strings en pointeurs de fonction.

Sinon, tu es obligé de modifier le code de ta classe à chaque fois, de connaître toutes les fonctions qui font intervenir avant de définir ton constructeur.

Je trouve que ça rend le code mal découpé et moins synthétique.

-----

sinon, pour boost variant, j'avais essayé de regarder un peu.. je connais mal, donc je me trompe peut etre, mais je ne suis ps sur que ca corresponde a ce que je veux. en effet, je ne vais pas avoir seulement a l'evaluer, mais aussi a faire des manipulations plus complexe, a parcourir l'arbre dans tous les sens... donc chacun de mes "types/genre/classe fille" va avoir des metodes assez particuliere...

Mais le type boost::variant que j'ai défini est la définition d'une expression sous forme arborescente selon la définition que je t'ai montrée !

Tu le manipules exactement comme un arbre.
Tu traites chacun des sous-types séparément (c'est pour ça qu'on définit plusieurs fonctions dans le visiteur).

Tu peux enlever la fonction unaire englobant une expression si elle existe par exemple, très facilement.

Optimisation / parser mathématique

C++

Discussions similaires

Partager

Partager