Salut, voila je suis entrain de faire une fonction qui permet la simplification d'expressions mathematiques (de base pour le moment), un espece de calculette à la noix quoi (du style celle de PowerTools sous Windows).    
 
L'utilisateur rentre une expression : "f(x)=1+x", ca enregistre la fonction dans un environnement. Il peut lancer une evaluation : "f(1)",  obtenir la derivée ou simplifier le corps de la fonction (du style "f(x)=1+2+x" => "f(x)=3+x" ) mais il y a un hic.
 
Le parseur construit (grace a des operations semantiques) un arbre prefixé de l'expression :
 
1+2-3 => (- (+ 1 2) 3) On obtient donc un arbre. (pas forcement binaire dans certains cas)
 
J'ai fait donc un simplificateur (ou évaluateur partiels) assez "bidon" qui se balade dans l'arbre recursivement et des qu'il croise une racine "+" verifie que ses deux fils sont des nombres pour cree une feuille (qui est le resultat de l'addition des deux fils) à la place de la racine, le probleme c'est qu'evidement il ne gere pas la simplification d'une expression comme "1+x-1" car en prefixé ca donne "(- (+ x 1) 1)" ou le sous arbre "(+ x 1)" n'est pas simplifiable.
 
J'ai pensé d'abord à faire un tri qui regroupe toutes les constantes dans un sous arbre et les variables dans l'autre ... c'est tres couteux et ca ne donne pas forcement de resultat satisfaisant. Ensuite, on pourrais faire de la simplification pendant le parsage , mais c'est tres light car se limite à des choses comme x*0=0 ou x*1=x etc ...
 
J'ai pas vraiment trouvé de choses interresantes (comme les algos utilisé dans les progs comme Mapple ou Mathematica dans le dernier un expression comme x²+x est équivalente, si ce n'est égale à x(x+1)), tout conseil ou avis serai fort agréable    
 
Merci.
 
 

Personne n'a rien a dire ?

Tu pourrais essayer de construire tous les arbres possibles en tirant partie de la commutativité et voir lequel est le meilleur.

Hhhmm oué ... t'as pas un exemple stp ?

Dans ton exemple 1+x-1 = x+1-1
Tu construis les deux arbres (- (+ x 1) 1) et (+ (-1 1) x). Le deuxieme se simplifie.

Ouala, tu regroupes d'un côté les constants, et de l'autre les variables

retrox => Ok et pour un arbre du genre (+ (+ x 1) (- x 1)) tu fait comment ? ... le probleme c'est que je construit l'arbre en parsant donc "changer" l'arbre en cours de parsage selon un critere est impossible, ou alors je vois pas du tout comment faire.
 
EDIT: Au depart j'obtiens ca et rien d'autre : (- (+ x 1) 1) justement mon but est d'obtenir un autre arbre à partir du premier (+ (-1 1) x).

Peut-être en changeant la méthode de création de l'arbre... D'abord tu groupes les membres, et après tu passes à la création de l'arbre

Et en ne travaillant qu'avec deux opérations ?
Après tout, 1 + x - 1 = 1 + x + (-1)
Dans ton arbre, tu obtiens quelque chose genre  
(+ ( 1 x (-1) ) )...
Et pareil, une division par a c'est une multiplication par (1/a)...

Oué je me suis fixé sur cette idée mais je gere aussi le cas du moins binaire ... j'ai mon arbre, je fait un petit parcours infixe dessus et je rempli une table de hashage (une TreeMap, je le fait en Java) en comptabilisant les apparitions des tous les termes (et leurs signe) qui sont presents dans l'arbre, j'obtient un truc du genre "pseudo" forme polynomiale quoi :
 
Terme : exp = 0
Terme : sin = 0
Terme : sin(1+x) = 1
Terme : sin(1+x+x2) = 0
Terme : x^0 = 0
Terme : x^1 = -1
Terme : x^2 = 2
Terme : x^3 = 0
 
Il me reste plus qu'a recontruire l'arbre en prefixe à partir de cette forme polynomiale (une somme des termes) pour avoir un truc exploitable. (derivable, integrable etc ...)
 
Bon si quelqu'un a une meilleure idée je suis preneur

 
Haha, c'est juissif quand ca marche !
 
Par contre l'algo que j'utilise pour remplir la HashMap est assez restrictif ... c'est un simple parcours recursif de l'arbre qui "ajoute" reelement les choses dans la table que quand il atteint les feuilles. Il ne permet pas de gerer les cas du style (x+x)^2 ou sin(x+2+x) qui necessite un pre-traitement (devellopement ou simplification des sous-arbres). Donc niveau complexité ca explose assez rapidement je pense.  
 
Si par hasard quelqu'un tombe sur les sources (des fonctions "expand" ou autre) de Maple ou un truc du genre ou il font ce genre de choses en langage imperatif ... partagez