Discussion :

[Premium]

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

[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

[Premium]

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?

[Trap D]

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

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
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.

[xxiemeciel]

Salut,

voici comment je l'aurais fait :

Code :

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

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

[xxiemeciel]

Un autre truc tu peux creer un arbre a partir de ton expression

+*12x

Code :

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

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

[Premium]

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

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
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.

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 ?

[Premium]

Salut,

voici comment je l'aurais fait :

Code :

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

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?

[Premium]

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

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
/*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 :

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

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.

[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?

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

[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 :

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
 
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 :

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
 
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

[Jedai]

Alors voyons ce que ça donne en OCaml :

Code :

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

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 ). 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ï

[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:

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

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 :

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

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 :

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

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.