#include <stdio.h>
#include <stdlib.h>

/* 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;
}

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);
}


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(new_op(t->contenu.op.name,derive(arg1,var),derive(arg2,var)));
    case '*':
      r1 = new_op('*',derive(arg1,var),arg2);
      r2 = new_op('*',arg1,derive(arg2,var));
      return(new_op('+',r1,r2));
    case '/':
      r1 = new_op('*',derive(arg1,var),arg2);
      r2 = new_op('*',arg1,derive(arg2,var));
      return(new_op('/',new_op('-',r1,r2),new_op('*',arg2,arg2)));
    default:
      fprintf(stderr,"deriv, mauvais operateur : %c\n",t->contenu.op.name);
      exit(-1);
    }
  }
}

void main(void)
{
  char pgm[] = "x1+y2-*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(new_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");
  }
}