Evaluation/simplification d'expression arithmetique

Version imprimable

06/12/2005, 16h58
Premium

Evaluation/simplification d'expression arithmetique

Bonjour,

j'aimerais avoir une aide concernant l'evaluation ou la simplification d'une expression arithmetique de la forme:
+ * 1 2 x qui doit renvoyer 2+x s'il n'a pas été affecté de valeur à x et le résultat sous forme de réel sinon:si x a été définit comme valant 2, le résultat serait:
+ * 1 2 x donne 1*2+x->4
Voici un lien qui donne des exemples
lien
06/12/2005, 18h37
xxiemeciel

Salut,

c'est le genre de chose qui se fait tres bien avec des fonctions recursives.

puisque apparement ton expression sera toujours de la forme

operateur valeur1 valeur2

avec valeur1 et valeur2 qui peuvent eux meme etre des expressions

XXiemeciel
06/12/2005, 18h55
Premium

Citation:

Envoyé par xxiemeciel

Salut,

c'est le genre de chose qui se fait tres bien avec des fonctions recursives.

puisque apparement ton expression sera toujours de la forme

operateur valeur1 valeur2

avec valeur1 et valeur2 qui peuvent eux meme etre des expressions

XXiemeciel

Est ce que tu as une idée sur la manière de procéder?

Salut
La fonction devrait être à peu près comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 fonction eval_exp retourne réel debut lex <- get_lexeme() choix (lex) cas Plus : val1 <- eval_exp val2 <- eval_exp retourner val1 + val2 cas Multiplier : val1 <- eval_exp val2 <- eval_exp retourner val1 * val2 ....................................... ....................................... cas Nombre: retourner valeur(nombre) cas Variable : retourner valeur(variable) fin choix fin
En considérant que la fonction get_lexeme(), qui est un analyseur lexical, étudie l'entrée et renvoie
Plus si le le signe + a été rencontré
Multiplier si le signe * a été rencontré
..........
Nombre si un nombre a été rencontré, sa valeur est obtenue en interrogeant l'analyseur lexical
Variable si le nom d'une variable a été rencontré, la valeur de la variable est obtenue en interrogeant le composant de ton programme chargé de gérer les variables déc;arées.

06/12/2005, 23h26
xxiemeciel
Salut,

voici comment je l'aurais fait :
Code:

1 2 3 4 5 6 double eval(Expression exp) { return exp.operateur(eval(exp.valeur1()),eval(exp.valeur2())); }
tu dois juste parcourir ton expression pour determiner valeur1 et valeur2, dans ton exemple +*12x

+ = operateur
*12 = valeur1
x = valeur2

et pour valeur1 :
* = operateur
1 = valeur1
2 = valeur2

XXiemeciel
07/12/2005, 03h45
xxiemeciel
Un autre truc tu peux creer un arbre a partir de ton expression

+*12x
Code:

1 2 3 4 5 6 7 8 9 10 + | ------------- | | * x | -------- | | 1 2
a partir de la le calcul devient simple. L'arbre est facile a creer, un operateur va generer deux fils et une valeur est forcement une feuille.

XXiemeciel

Citation:
Envoyé par Trap D
Salut
La fonction devrait être à peu près comme ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 fonction eval_exp retourne réel debut lex <- get_lexeme() choix (lex) cas Plus : val1 <- eval_exp val2 <- eval_exp retourner val1 + val2 cas Multiplier : val1 <- eval_exp val2 <- eval_exp retourner val1 * val2 ....................................... ....................................... cas Nombre: retourner valeur(nombre) cas Variable : retourner valeur(variable) fin choix fin
En considérant que la fonction get_lexeme(), qui est un analyseur lexical, étudie l'entrée et renvoie
Plus si le le signe + a été rencontré
Multiplier si le signe * a été rencontré
..........
Nombre si un nombre a été rencontré, sa valeur est obtenue en interrogeant l'analyseur lexical
Variable si le nom d'une variable a été rencontré, la valeur de la variable est obtenue en interrogeant le composant de ton programme chargé de gérer les variables déc;arées.
Citation:

cas Variable :
retourner valeur(variable)

La variable n'est pas forcée d'avoir une valeur durant les calculs .
Dans ce cas,il ne faut simplifier que ce qui peut l'etre (les réels + les variables qui ont une valeur).
Si tous les éléments qui constituent l'expression ont une valeur réelle alors le résultat sera un réel.
Dans l'algo que tu as mis cela fonctionne lorsque toutes les termes de l'expression ont une valeur mais comment faire lorsque ce n'est pas le cas ?

07/12/2005, 07h26
Premium
Citation:
Envoyé par xxiemeciel

Salut,

voici comment je l'aurais fait :

Code:

1 2 3 4 5 6 double eval(Expression exp) { return exp.operateur(eval(exp.valeur1()),eval(exp.valeur2())); }

tu dois juste parcourir ton expression pour determiner valeur1 et valeur2, dans ton exemple +*12x

+ = operateur
*12 = valeur1
x = valeur2

et pour valeur1 :
* = operateur
1 = valeur1
2 = valeur2

XXiemeciel
La fonction que tu as appelé eval renvoye un double mais si dans le cas ou x n'a pas de valeur qui lui a été affectée,la calculatrice parcours la chaine préfixe et renvoye en infixe:
1*2+x->2+x car je n'ai pas effecté de valeur à x.
L'utilisateur de la calculatrice,peux ne jamais avoir envie d'affecter une valeur à x.
Comment faire dans ce cas?

Voici ce que j'ai crée comme structure pour mon arbre
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 /*Types de noeuds dans une expression:operateur, constante, variable*/ enum TypeInfoExpr {InfoExprOp, InfoExprCte, InfoExprVar}; union InfoExpr /*une info dans une expression*/ { double cte;/*constante*/ char *nom;/*variable*/ char op;/*operateur*/ }; /*Une expression est un arbre binaire Le sous arbre droit d'un operateur unaire est vide Les sous arbres d'expressions constante ou variable sont vides*/ typedef struct noeud { enum TypeInfoExpr type;/*le type de l'information de ce noeud*/ union InfoExpr info;/*l'information*/ struct noeud *gauche,*droit;/*expression gauche,droite*/ }Noeud,*Expression;
J'ai créer une fonction:

Code:

int AddVariable(const char *nom, int type, double val)

qui permet de savoir si la variable a une valeur qui lui a été affectée ou non.
Si c'est le cas la fonction renvoye la valeur et un nombre très grand dans la cas contraire.

Est ce que vous pouvez m'indiquer une méthode avec ce que j'ai crée,si il y a des ajouts ou suppression à faire concernant la structure de l'arbre.

07/12/2005, 18h04
xxiemeciel

Citation:

Envoyé par Man_Utd

La fonction que tu as appelé eval renvoye un double mais si dans le cas ou x n'a pas de valeur qui lui a été affectée,la calculatrice parcours la chaine préfixe et renvoye en infixe:
1*2+x->2+x car je n'ai pas effecté de valeur à x.
L'utilisateur de la calculatrice,peux ne jamais avoir envie d'affecter une valeur à x.
Comment faire dans ce cas?

dans ce cas tu retournes un objet Valeur a la place d'un double et les fonctions valeur1() et valeur2() retourneraons des objets valeur aussi.

XXiemeciel

ca aurait été bien plus beau et pratique avec un peu de prog objet.

sinon je pense tu auras besoin que ton noeud connaisse son noeud parent aussi sinon tu auras du mal a remonter quand tu arriveras sur les feuilles de ton arbre. Mais je suis pas sur que ce soit oblige.

au niveau de l'algorithme de remplissage de l'arbre tu prend ton expression et tu la lis de la gauche vers la droite.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Expression = "+*12x"
 
premier Noeud 1  <- + : operateur donc remplissage des fils 
(Expression = "+12x")
 
fils gauche 1 <- * : operateur donc remplissage de ces fils
(Expression = "12x")
 
fils gauche 2 <- 1 : valeur donc on remonte au parent (qui est gauche 1)
(Expression = "2x")
 
fils droit 2 <- 2 : valeur donc on remonte au parent (qui est gauche 1)
(Expression = "x")
 
fils droit 1 <- x : valeur et expression est vide donc c terminee

en code recursif ca donnerais ceci :

Code:

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
 
Expression = "+*12x";
 
//remplir s'appelle sur un noeud (this)
Expression remplir(Expression)
{
       if(Expression == "") return; //c terminee
 
       if(Expression.premier.EstUnOperateur())
       {
             this->Contenu = Expression.premier();
 
             //la methode enlevePremier enleve le premier element
             //de l'expression et retourne une expression
             NewExpression =  
                  this->filsGauche()->remplir(Expression.EnlevePremier());
             NewExpression =
                  this->filsDroit()->remplir(NewExpression);
 
             return NewExpression;
       }
       else
       {
             this->Contenu = Expression.premier();
 
             return  Expression.EnlevePremier();
       }
}

XXiemeciel

Alors voyons ce que ça donne en OCaml :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 type expr = Float of float | Var of string | Plus of expr * expr | Mult of expr * expr type environnement = (string * float) list let rec reduce env = function | Float(f) -> Float(f) | Var(s) -> ( try Float( List.assoc env s ) with Not_found -> Var(s) ) | Plus(e, e') -> ( match ( reduce env e, reduce env e' ) with | (Float(f), Float(f')) -> Float( f +. f' ) | other -> Plus( other ) ) | Mult(e, e') -> ( match ( reduce env e, reduce env e' ) with | (Float(f), Float(f')) -> Float( f *. f' ) | other -> Mult( other ) )
Ceci est un code basique, mais fonctionnel (dans tous les sens du terme :wink: ). Reste à implémenter l'associativité, la commutativité, etc...

(Le parser associé est aussi simple que la fonction reduce)

(EDIT : en regardant les exemples, je vois que le but est un peu plus complexe (définition de fonctions par exemple), ayant déjà implémenté un langage plus complexe en OCaml, je peux te dire que ce n'est pas beaucoup plus compliqué que ce que j'ai mis juste au-dessus, de plus OCaml dispose d'outils équivalents à yacc et lex pour réaliser facilement le parser)

--
Jedaï

08/12/2005, 12h19
DrTopos
Bonjour à tous.

Je vous propose de prendre de problème d'un peu plus haut. Il s'agit en effet d'un problème de réécriture, or la théorie de la réécriture n'en est plus tout à fait à ses débuts.

Un système de réécriture est un ensemble de règles (un peu comme des règles de grammaire formelle). Chaque règle a un membre de gauche et un membre de droite. Utiliser la règle consiste à remplacer une occurence du membre de gauche (qu'on appelle un redex) par le membre de droite. Normaliser une expression consiste à lui appliquer les règles de réécriture jusqu'à ce que plus aucune d'entre elles ne soit applicable. C'est bien exactement ce qu'on veut faire ici sur des expressions qui ne sont pas numériques mais symboliques (c'est à dire qui contiennent des symboles, représentant des nombres arbitraires).

La réécriture pose deux problèmes, qui ont été étudiés pour la première fois par le créateur du lambda-calcul: Alonzo Church (années 30). Ces problèmes sont les suivants:

:arrow: Noethériannité: la réécriture s'arrête-t-elle ou est-il possible de réécrire une expression indéfiniement ?

:arrow: Confluence (encore appelée propriété de Church-Rosser): si on fait des choix différents dans les redex à réduite (à réécrire), arrive-t-on à la fin au même résultat ?

Un système de réécriture est dit canonique s'il vérifie ces deux propriétés, c'est à dire si toute normalisation se termine et si le résultat est indépendant de la façon de s'y prendre.

Le lambda-calcul non typé n'est pas noethérien. L'exemple est célèbre et s'appelle combinateur paradoxal de Curry. Par contre le lambda-calcul typé est noethérien et confluent. C'est un théorème difficile (théorème de W.W. Tait) datant des années 60, mais qui démontre bien l'importance du typage.

Toute la question est donc d'établir les règles de réécriture pour le problème posé et de montrer que le système est canonique. Une fois que c'est fait, c'est de la simple routine d'écrire le programme. Je recommande d'ailleurs d'écrire une fois pour toutes un méta-programme capable d'utiliser directement les règles de réécriture. De cette façon, les modifications seront très faciles à faire.

En général, faire un système de réécriture, consiste d'abord à partir d'une sémantique équationnelle, c'est à dire d'un ensemble d'équations (axiomes) définissant le sens de l'égalité entre expressions. Par exemple, des équations telles que celles-ci peuvent en faire partie:
Code:

1 2 3 4 (x+y)*z = x*z + y*z (x*y)*z = x*(y*z) etc...
Une fois que c'est fait, la relation d'équivalence engendrée par ces équations est (par définition) la relation d'égalité entre expressions.

Transformer cette sémantique équationnelle en système de réécriture consiste dans un premier temps à orienter ces équations pour en faire des règles de réécriture. Par exemple, on peut imaginer d'orienter la première règle ci-dessus en:
Code:

1 2 (x+y)*z --> x*z + y*z
Si on parvient à le faire de telle façon que le système de réécriture obtenu soit canonique, c'est gagné. Mais ça peut être difficile, et ça peut nécessiter l'introdution des expressions et de règles supplémentaires. Apparemment, les expressions dont il s'agit ici sont essentiellment polynômiales. Il faut donc aller dans le sens du développement et non dans celui de la factorisation de ces polynôme, laquelle serait sans espoir.

La confluence est automatique s'il n'y a pas de paire critique. Une paire critique est la présence de deux redex qui se recouvrent partiellement. Si deux redex n'ont pas de partie commune, on peut les réduire l'un après l'autre dans n'importe quel ordre on obtient le même résultat. Par contre, s'il y a une paire critique, le fait de choisir de réduire l'un d'eux détruit l'autre, et la confluence devient un vrai problème. Il y a un théorème (théorème de Knuth-Bendix) qui dit que la confluence (globale) résulte d'une propriété de confluence locale. Ce théorème rend en général assez facile la preuve de la confluence.

Pour la noethériannité, il y a des méthodes naïves qui marchent parfois, qui consistent à montrer que le nombre de certains symboles diminue strictement à chaque réduction. Comme il ne peut pas diminuer indéfiniment, la noethériannité en résulte. Mais très souvent, ces méthodes naïves ne suffisent pas.

Le livre Canonical Forms in Finitely Presented Algebras d'Yves Le Chenadec (édité chez Pitman/Wiley) contient de nombreux exemples, y compris proches du problème d'expressions arithmétiques posé ici.