Simplification d'une expresion

   1. #include <stdio.h>
   2. #include <string.h>
   3. #include <stdlib.h>
   4. #include <ctype.h>
   5.
   6.
   7. enum Type {Operateur, Constante, Variable};
   8.
   9.
  10. union Info
  11. {
  12.   double cte;
  13.   char *nom;
  14.   char op;
  15. };
  16.
  17. struct noeud{
  18.   enum Type type;
  19.   union Info info;
  20.   struct noeud *gauche;
  21.   struct noeud *droit;
  22. };
  23.
  24. typedef struct noeud Noeud;
  25. typedef struct noeud * Expression;
  26.
  27.
  28. Expression AnalyseExpression(char **ligne)
  29. {
  30.  
  31.   Expression e;
  32.   char c;
  33.  
  34.   while(**ligne == ' ') (*ligne)++;
  35.  
  36.   /* on est en fin de chaine */
  37.   if(**ligne == '\0')
  38.     {
  39.       fprintf(stderr,"erreur : il doit manquer des operandes\n");
  40.       return NULL;
  41.     }
  42.  
  43.   e = (Expression)malloc(sizeof(Noeud));
  44.   if(e == NULL) return e;
  45.  
  46.   /* c'est un chiffre */
  47.   if(isdigit(**ligne))
  48.     {
  49.       e->type = Constante;
  50.       sscanf(*ligne,"%lf ",&(e->info.cte));
  51.       while(isdigit(**ligne) || **ligne == '.') (*ligne)++;
  52.     }
  53.  
  54.   else
  55.     {
  56.       /* c'est une lettre */
  57.       if(isalpha(**ligne))
  58.     {
  59.       e->type = Variable;
  60.       sscanf(*ligne,"%s ",e->info.nom);
  61.       while(isalpha(**ligne)) (*ligne)++;
  62.     }
  63.       else
  64.     {
  65.       /* le caractere est un operateur */
  66.       c=*((*ligne)++);
  67.       if(c == '+' || c == '-' || c == '*' || c == '/')
  68.         {
  69.           e->type = Operateur;
  70.           e->info.op = c;
  71.           e->gauche = AnalyseExpression(ligne);
  72.           e->droit = AnalyseExpression(ligne);
  73.         }
  74.       else if(c == '@' || c == '~')
  75.         {
  76.           e->type = Operateur;
  77.           e->info.op = c;
  78.           e->gauche = AnalyseExpression(ligne);
  79.           e->droit = NULL;
  80.         }
  81.       else printf("Erreur,'%c' n'est pas un operateur prevu\n",c);
  82.     }
  83.     }
  84.   return e;
  85. }
  86.
  87.
  88.
  89. /* Affichage de l'arbre en infixe */
  90. void Infixe(Expression e)
  91. {
  92.   switch(e->type)
  93.     {
  94.     case Constante:
  95.       printf("%f",e->info.cte);
  96.       break;
  97.      
  98.     case Variable:
  99.       printf("%s",e->info.nom);
 100.       break;
 101.      
 102.     case Operateur:
 103.       switch(e->info.op)
 104.     {
 105.       case'+':
 106.         case'-':/* affichage infixe sans () */
 107.         Infixe(e->gauche);
 108.       if(e->info.op == '+') printf("+");
 109.       else printf("-");
 110.       Infixe(e->droit);
 111.       break;
 112.       case'*':
 113.         case'/':/* affichage infixe avec () */
 114.         if(e->gauche->type != Operateur)
 115.           Infixe(e->gauche);
 116.         else
 117.           {
 118.         printf("(");
 119.         Infixe(e->gauche);
 120.         printf(")");
 121.           }
 122.       if(e->info.op == '*') printf("*");
 123.       else printf("/");
 124.      
 125.       if(e->droit->type != Operateur)
 126.         Infixe(e->droit);
 127.       else
 128.         {
 129.           printf("(");
 130.           Infixe(e->droit);
 131.           printf(")");
 132.         }
 133.       break;
 134.       case'@':/* affichage prefixe */
 135.         printf("@");
 136.       Infixe(e->gauche);
 137.       break;
 138.       case'~':
 139.         printf("~");
 140.       Infixe(e->gauche);
 141.       break;
 142.     }
 143.     }
 144. }
 145.
 146.
 147. double Eval(Expression *e)
 148. {
 149.   double r1,r2;
 150.  
 151.   if((*e)->type == Constante) return((*e)->info.cte);
 152.  
 153.   if ((*e)->type == Operateur)
 154.     {
 155.       r1=Eval(&(*e)->gauche);
 156.       r2=Eval(&(*e)->droit);
 157.       switch ((*e)->info.op)
 158.     {
 159.     case '+':return(r1+r2);
 160.     case '-':return(r1-r2);
 161.     case '*':return(r1*r2);
 162.     case '/':return(r1/r2);
 163.     }
 164.     }
 165.   /* si aucun return n'a t effectu jusqu'ici*/
 166.   puts("erreur (code opratoire inconnu par exemple)");
 167.   return(0);
 168. }
 169.
 170. double (*FonctionOperateur(char operateur))(double, double)
 171. {
 172.   char ops[]={'+','-','*','/','\0'};
 173.   double (*fcts[])(double,double)={Plus,Moins,Mul,Div,NULL};
 174.   unsigned i;
 175.   for(i=0;fcts[i]!=NULL&&ops[i]!=operateur;++i);
 176.   return fcts[i];
 177. }
 178.
 179.
 180. int main (void)
 181. {
 182.   double res;
 183.   char *ligne = "* + 1 2 3";
 184.   Expression e = NULL;
 185.   e=AnalyseExpression(&ligne);
 186.   Infixe(e);
 187.   printf("->");
 188.   res=Eval(&e);
 189.   printf("%lf",res);
 190.   printf("\n");
 191.   return 0;
 192.  
 193. }