/*********************************************************   
  TD d'Algorithmique IN202    
  ENSTA  
  Manipulation d'expressions mathematiques   
  Derivation formelle                    Guillaume Poupard    
*********************************************************/  
#include <stdio.h>  
#include <stdlib.h>   
#include <string.h>  
struct Element{  
  int type;   
  int val;
  char op;
  char fonc[4];
};  

struct noeud{   
  struct Element elt;  
  struct noeud *fg;   
  struct noeud *fd; 
};   
  
typedef struct noeud *Arbre;   
  
Arbre branche(int t, int v, char o, char *f, Arbre g, Arbre d)   
{  
  Arbre nouv;   
  nouv=(Arbre) malloc(sizeof(struct noeud));  
  nouv->elt.type=t;   
  nouv->elt.val=v;  
  nouv->elt.op=o; 
 strcpy(nouv->elt.fonc,f);  
  nouv->fg=g;   
  nouv->fd=d;  
  return nouv;   
}  
   
void prefixe(Arbre a)  
{   
  if (a!=NULL)  
    {   
      switch (a->elt.type)  
        {   
        case 1:  
          printf("%d ",a->elt.val);   
          break;  
        case 2:   
          printf("%c ",a->elt.op);  
          prefixe(a->fg);   
          prefixe(a->fd);  
          break;   
        case 3:  
          printf("%s ",a->elt.fonc);   
          prefixe(a->fg);  
          break;   
        case 4:  
          printf("x ");   
        }  
    }   
}  
   
void infixe(Arbre a)  
{   
  if (a!=NULL)  
    {   
      switch (a->elt.type)  
        {   
        case 1:  
          printf("%d",a->elt.val);   
          break;  
        case 2:   
          printf("(");  
          infixe(a->fg);  
          printf("%c",a->elt.op);  
          infixe(a->fd);   
          printf(")");  
          break;   
        case 3:  
          printf("%s(",a->elt.fonc);   
          infixe(a->fg);  
          printf(")");   
          break;  
        case 4:   
          printf("x");  
        }   
    }  
}   
Arbre copie(Arbre a)  
{   
  if (a==NULL)  
    return NULL;   
  else  
    return branche(a->elt.type,a->elt.val,a->elt.op,a->elt.fonc,   
                   copie(a->fg), 
                   copie(a->fd));  
} 
  
Arbre derive(Arbre a) 
{  
  if (a==NULL) 
    return NULL;  
  switch (a->elt.type) 
    {  
    case 1: 
      return branche(1,0,' ',"",  
                     NULL, 
                     NULL);  
    case 2: 
      switch (a->elt.op)  
        { 
        case '+':  
          return branche(2,0,'+',"", 
                         derive(a->fg),  
                         derive(a->fd)); 
        case '-':  
          return branche(2,0,'-',"", 
                         derive(a->fg),  
                         derive(a->fd)); 
        case '*':  
          return branche(2,0,'+',"", 
                         branche(2,0,'*',"",  
                                 derive(a->fg), 
                                 copie(a->fd)),  
                         branche(2,0,'*',"", 
                                 copie(a->fg),  
                                 derive(a->fd))); 
        // Ajouter la division    
        }                  
    case 3:  
      if (strcmp("sin",a->elt.fonc)==0) 
        return branche(2,0,'*',"",derive(a->fg),  
                       branche(3,0,' ',"cos", 
                               copie(a->fg),  
                               NULL)); 
      if (strcmp("cos",a->elt.fonc)==0)  
        return branche(2,0,'*',"", 
                       branche(1,-1,' ',"",  
                               NULL, 
                               NULL),  
                       branche(2,0,'*',"", 
                               derive(a->fg),  
                               branche(3,0,' ',"sin", 
                                       copie(a->fg),  
                                       NULL))); 
      // Ajouter toutes les fonctions voulues  
    case 4: 
      return branche(1,1,' ',"",  
                     NULL, 
                     NULL);  
    } 
}
 
Arbre simplifie(Arbre a)  
{ 
  if (a==NULL)  
    return NULL; 
  switch (a->elt.type)  
    { 
    case 1:  
      return branche(1,a->elt.val,' ',"", 
                     NULL,  
                     NULL); 
    case 2:  
      if ((a->fg->elt.type==1) && (a->fd->elt.type==1)) 
        switch (a->elt.op)  
          { 
          case '+':  
            return branche(1,a->fg->elt.val+a->fd->elt.val,' ',"", 
                           NULL,  
                           NULL); 
          case '-':  
            return branche(1,a->fg->elt.val-a->fd->elt.val,' ',"", 
                           NULL,  
                           NULL); 
          case '*':  
            return branche(1,a->fg->elt.val*a->fd->elt.val,' ',"", 
                           NULL,  
                           NULL); 
        // Ajouter la division    
          } 
      if (a->elt.op=='+')  
        { 
          if ((a->fg->elt.type==1) && (a->fg->elt.val==0))  
            return simplifie(a->fd); 
          if ((a->fd->elt.type==1) && (a->fd->elt.val==0))  
            return simplifie(a->fg); 
        }  
      if (a->elt.op=='-') 
        {  
          if ((a->fd->elt.type==1) && (a->fd->elt.val==0)) 
            return simplifie(a->fg);  
        } 
      if (a->elt.op=='*')  
        { 
          if ((a->fg->elt.type==1) && (a->fg->elt.val==0))  
            return branche(1,0,' ',"", 
                           NULL,  
                           NULL); 
          if ((a->fg->elt.type==1) && (a->fg->elt.val==1))  
            return simplifie(a->fd); 
          if ((a->fd->elt.type==1) && (a->fd->elt.val==0))  
            return branche(1,0,' ',"", 
                           NULL,  
                           NULL); 
          if ((a->fd->elt.type==1) && (a->fd->elt.val==1))  
            return simplifie(a->fg); 
        }  
        // Ajouter la division   
      return branche(a->elt.type,a->elt.val,a->elt.op,a->elt.fonc,  
                     simplifie(a->fg), 
                     simplifie(a->fd));  
    case 3: 
      return branche(a->elt.type,a->elt.val,a->elt.op,a->elt.fonc,  
                     simplifie(a->fg), 
                     NULL);  
    case 4:  
      return branche(a->elt.type,a->elt.val,a->elt.op,a->elt.fonc,  
                     NULL, 
                     NULL);  
    } 
}  
 
  
int main(int argc, char * argv[]) 
{  
  Arbre exemple; 
  exemple=branche(2,0,'-',"",  
                  branche(2,0,'*',"", 
                          branche(2,0,'+',"",
                                  branche(4,0,' ',"",NULL,NULL), 
                                  branche(1,2,' ',"",NULL,NULL)),  
                          branche(3,0,' ',"sin", 
                                  branche(2,0,'*',"",  
                                          branche(4,0,' ',"",NULL,NULL), 
                                          branche(4,0,' ',"",NULL,NULL)),  
                                  NULL)), 
                  branche(3,0,' ',"cos",  
                          branche(4,0,' ',"",NULL,NULL), 
                          NULL));  
  printf("Expression     : "); 
  infixe(exemple);  
  printf("\nCopie          : "); 
  infixe(copie(exemple));  
  printf("\nDerivee        : "); 
  infixe(derive(exemple));  
  exemple=simplifie(derive(exemple)); 
  printf("\nSimplification : ");  
  infixe(exemple); 
  exemple=simplifie(exemple);  
  printf("\nSimplification : "); 
  infixe(exemple);  
  exemple=simplifie(exemple); 
  printf("\nSimplification : ");  
  infixe(exemple); 
  printf("\n");  
  exit(0); 
  }