#include #include /**********/ /* Arbres */ /**********/ typedef enum {Var, Num, Op} Nature; typedef union { char name; int val; struct op { char name; struct tcell *gauche,*droite; } op; } Contenu; typedef struct tcell { Nature nature; Contenu contenu; } *Tree; Tree new_var(char name) { Tree r; r = (Tree)malloc(sizeof(struct tcell)); if (r == NULL) { fprintf(stderr,"Plus de memoire\n"); exit(-1); } r->nature = Var; r->contenu.name = name; return r; } char as_var(Tree t) { if (t->nature != Var) { fprintf(stderr,"Var attendu\n"); exit(-1); } return t->contenu.name; } Tree new_num(int val) { Tree r; r = (Tree)malloc(sizeof(struct tcell)); if (r == NULL) { fprintf(stderr,"Plus de memoire\n"); exit(-1); } r->nature = Num; r->contenu.val = val; return r; } int is_num(Tree t) { return t->nature == Num; } int as_num(Tree t) { if (t->nature == Num) { return t->contenu.val; } fprintf(stderr,"echec, is_num\n"); exit(-1); } Tree new_op(char name,Tree gauche,Tree droite) { Tree r; r = (Tree)malloc(sizeof(struct tcell)); if (r == NULL) { fprintf(stderr,"Plus de memoire\n"); exit(-1); } r->nature = Op; r->contenu.op.name = name; r->contenu.op.gauche = gauche; r->contenu.op.droite = droite; return r; } void print_tree(Tree t) { if (t != NULL) { if (t->nature == Var) printf("%c",t->contenu.name); else if (t->nature == Num) printf("%d",t->contenu.val); else { putchar('('); print_tree(t->contenu.op.gauche); putchar(t->contenu.op.name); print_tree(t->contenu.op.droite); putchar(')'); } } } /*********/ /* Piles */ /*********/ typedef struct lcell { Tree val; struct lcell *next; } Cell, *Stack; Stack stack = NULL; Cell *cons(Tree val,Cell *next) { Cell *r; r = (Cell *)malloc(sizeof(Cell)); if ( r == NULL) { fprintf(stderr,"Plus de memoire\n"); exit(-1); } r->val = val; r->next = next; return r; } void afficher(void) { Stack p; printf("["); for (p=stack ; p != NULL ; p = p->next) { print_tree(p->val); if (p->next != NULL) printf(", "); } printf("]"); } Tree pop(void) { Tree r; Stack tmp; if (stack == NULL) { fprintf(stderr,"Tentative de depiler une pile vide, adieu\n"); exit(-1); } r = stack->val; tmp = stack; stack = stack->next; free(tmp); return r; } void push(Tree i) { stack = cons(i,stack); } /****************************/ /* simplification des abres */ /****************************/ /* test de commutativite des operateurs */ int commute(char op) { return (op == '+') || (op == '*'); } /* Test d'egalite de arbres */ int egal(Tree t1,Tree t2) { if (t1->nature != t2->nature) return 0; if (t1->nature == Var) return as_var(t1) == as_var(t2); if (t1->nature == Num) return as_num(t1) == as_num(t2); /* cas des operateurs */ if (t1->contenu.op.name != t2->contenu.op.name) return 0; return (egal(t1->contenu.op.gauche,t2->contenu.op.gauche) && egal(t1->contenu.op.droite,t2->contenu.op.droite)) || (commute(t1->contenu.op.name) && (egal(t1->contenu.op.gauche,t2->contenu.op.droite) && egal(t1->contenu.op.droite,t2->contenu.op.gauche))); } /* simple_op ne construit pas certains noeud simplifiables */ Tree simple_op(char name,Tree arg1,Tree arg2) { /* deux arguments numeriques, calculer */ if (is_num(arg1) && is_num(arg2)) { int r1,r2; r1 = as_num(arg1); r2 = as_num(arg2); switch (name) { case '+': return new_num(r1+r2); case '-': return new_num(r1-r2); case '*': return new_num(r1*r2); case '/': return new_num(r1/r2); default: return new_op(name,arg1,arg2); } } /* echange des arguments pour les ope'rateurs commutatifs */ if (commute(name)) { if (is_num(arg2)) { Tree t; t = arg1; arg1 = arg2; arg2 = t; } } /* simplification de quelques premiers arguments cannoniques */ if (is_num(arg1)) { int r1 = as_num(arg1); switch (name) { case '+': if (r1 == 0) return arg2; else break; case '*': if (r1 == 0) return new_num(0); else if (r1 == 1) return arg2; else break; case '/': if (r1 == 0) return new_num(0); else break; default: } } /* simplification de quelques deuxiemes arguments cannoniques */ if (is_num(arg2)) { int r2 = as_num(arg2); switch (name) { case '-': if (r2 == 0) return arg1; else break; case '/': if (r2 == 1) return arg1; else break; default: } } /* simplification additionnelles */ switch (name) { case '-': if (egal(arg1,arg2)) return new_num(0); else break; case '/': if (egal(arg1,arg2)) return new_num(1); else break; case '+': if (egal(arg1,arg2)) return simple_op('*',new_num(2),arg1); else break; default: } /* pas de simplifications */ return new_op(name,arg1,arg2); } /**************/ /* Derivation */ /**************/ Tree derive(Tree t, char var) { if (t == NULL) return NULL; if (t->nature == Num) return new_num(0); else if (t->nature == Var) { if (t->contenu.name == var) return new_num(1); else return new_num(0); } else { Tree arg1,arg2,r1,r2; arg1 = t->contenu.op.gauche; arg2 = t->contenu.op.droite; switch (t->contenu.op.name) { case '-': case '+': return(simple_op(t->contenu.op.name,derive(arg1,var),derive(arg2,var))); case '*': r1 = simple_op('*',derive(arg1,var),arg2); r2 = simple_op('*',arg1,derive(arg2,var)); return(simple_op('+',r1,r2)); case '/': r1 = simple_op('*',derive(arg1,var),arg2); r2 = simple_op('*',arg1,derive(arg2,var)); return(simple_op('/',simple_op('-',r1,r2),simple_op('*',arg2,arg2))); default: fprintf(stderr,"deriv, mauvais operateur : %c\n",t->contenu.op.name); exit(-1); } } } /* calculatrice */ void main(void) { char pgm[] = "32x+3xy*-*+xd"; char c; int i; Tree r1,r2; printf(" "); afficher(); printf("\n"); for(i=0; pgm[i] != '\0'; i++) { c = pgm[i]; switch (c) { case '+': case '-': case '*': case '/': r1 = pop(); r2 = pop(); push(simple_op(c,r2,r1)); break; case 'd': r1 = pop(); r2 = pop(); push(derive(r2,as_var(r1))); break; default: if ('0' <= c && c <= '9') push(new_num(c - '0')); else if ('a' <= c && c < 'z') push(new_var(c)); } printf("%c : ",c); afficher(); printf("\n"); } }