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

typedef struct expr_{
  enum{produit, somme, etoile, a, b, epsilon, vide} type;
  struct expr_ *op1;  
  struct expr_ *op2;
} expr;


expr *E0(char *s, int *i);
expr *E1(char *s, int *i);
expr *E2(char *s, int *i);
expr *E3(char *s, int *i);
expr *E4(char *s, int *i);

expr *creer_a(void);
expr *creer_b(void);
expr *creer_epsilon(void);
expr *creer_vide(void);
expr *creer_etoile(expr *e);
expr *creer_somme(expr *e1, expr *e2);
expr *creer_produit(expr *e1, expr *e2);

expr *creer_a(void)
{
  expr *e = malloc(sizeof(expr));
  e->type = a;
  e->op1 = NULL;
  e->op2 = NULL;
  return e;
}

expr *creer_b(void)
{
  expr *e = malloc(sizeof(expr));
  e->type = b;
  e->op1 = NULL;
  e->op2 = NULL;
  return e;
}

expr *creer_epsilon(void)
{
  expr *e = malloc(sizeof(expr));
  e->type = epsilon;
  e->op1 = NULL;
  e->op2 = NULL;
  return e;
}

expr *creer_vide(void)
{
  expr *e = malloc(sizeof(expr));
  e->type = vide;
  e->op1 = NULL;
  e->op2 = NULL;
  return e;
}

expr *creer_etoile(expr *e1)
{
  expr *e = malloc(sizeof(expr));
  e->type = etoile;
  e->op1 = e1;
  e->op2 = NULL;
  return e;
}

expr *creer_somme(expr *e1, expr *e2)
{
  expr *e = malloc(sizeof(expr));
  e->type = somme;
  e->op1 = e1;
  e->op2 = e2;
  return e;
}

expr *creer_produit(expr *e1, expr *e2)
{
  expr *e = malloc(sizeof(expr));
  e->type = produit;
  e->op1 = e1;
  e->op2 = e2;
  return e;
}

expr *copie(expr *e)
{
  if(e == NULL) return NULL;
  if(e->type == produit) return creer_produit(copie(e->op1), copie(e->op2));
  if(e->type == etoile) return creer_etoile(copie(e->op1));
  if(e->type == somme) return creer_somme(copie(e->op1), copie(e->op2));
  if(e->type == a) return creer_a();
  if(e->type == b) return creer_b();
  if(e->type == epsilon) return creer_epsilon();
  if(e->type == vide) return creer_vide();
}

/*  E0 -> E1 + E0 | E1 */
expr *E0(char *s, int *i)
{
  expr *e;
  e = E1(s, i);
  if(s[*i] == '+'){
    *i = *i + 1;
    e = creer_somme(e, E0(s, i));
  }
  return e;
}

/*  E1 -> E2 . E1 | E2 */
expr *E1(char *s, int *i)
{
  expr *e;
  e = E2(s, i);
  if(s[*i] == '.'){
    *i = *i + 1;
    e = creer_produit(e, E1(s, i));
  }
  return e;
}
/* E2 -> E3 * | E3 */
expr *E2(char *s, int *i)
{
  expr *e;
  e = E3(s, i);
  if(s[*i] == '*'){
    *i = *i + 1;
    e = creer_etoile(e);
  }  
  return e;
}

/* E3 -> ( E0 ) | E4 */
expr *E3(char *s, int *i)
{
  expr *e;
  if(s[*i] == '('){
    *i = *i + 1;
    e = E0(s, i);
    if(s[*i] != ')')
      return NULL;
    *i = *i + 1;
  }
  else
    e = E4(s,i);
  return e;
}
/* e4 -> a | b | epsilon*/

expr *E4(char *s, int *i)
{
  expr *e = NULL;
  if(s[*i] == 'a'){
    *i = *i + 1;
    e = creer_a();
  }

  if(s[*i] == 'b'){
    *i = *i + 1;
    e = creer_b();
  }

  if(s[*i] == 'e'){
    *i = *i + 1;
    e = creer_epsilon();
  }
  return e;
}
void affiche_expr(expr *e)
{
  if(e == NULL) return;
  if(e->type == vide) printf ("v");
  if(e->type == epsilon) printf ("e");
  if(e->type == a) printf ("a");
  if(e->type == b) printf ("b");
  if(e->type == etoile){
    if((e->op1)&&((e->op1->type == somme) || (e->op1->type == produit))){
	printf("(");
	affiche_expr(e->op1);
	printf(")");
      }
      else
	affiche_expr(e->op1);
    printf("*");
  }
  if(e->type == somme){
    affiche_expr(e->op1);
    printf("+");
    affiche_expr(e->op2);
  }
  if(e->type == produit){
    if((e->op1) && (e->op1->type == somme)){
      printf("(");
      affiche_expr(e->op1);
      printf(")");
    }
    else
      affiche_expr(e->op1);

    printf(".");

    if((e->op2)&& (e->op2->type == somme)){
      printf("(");
      affiche_expr(e->op2);
      printf(")");
    }
    else
      affiche_expr(e->op2);
  }
}

int contient_epsilon(expr *e)
{
  if(e->type == produit) return (contient_epsilon(e->op1) && contient_epsilon(e->op2));
  if(e->type == etoile) return 1;
  if(e->type == somme)return (contient_epsilon(e->op1) || contient_epsilon(e->op2));
  if(e->type == a) return 0;
  if(e->type == b) return 0;
  if(e->type == epsilon) return 1;
  if(e->type == vide) return 0;
}

expr *residuel(expr *e, char c)
{
  if(e == NULL) return NULL;
  if(e->type == produit){
    if(contient_epsilon(e->op1))
      return creer_somme(creer_produit(residuel(e->op1, c), copie(e->op2)), residuel(e->op2, c));
    else
      return creer_produit(residuel(e->op1, c), e->op2);
  }
  if(e->type == etoile){
    return creer_produit(residuel(e->op1, c), creer_etoile(copie(e->op1))); 
  }
  if(e->type == somme){
    return creer_somme(residuel(e->op1, c), residuel(e->op2, c));
  }
  if(e->type == a){
    if(c == 'a') return creer_epsilon();
    else return creer_vide();
  }
  if(e->type == b){
    if(c == 'b') return creer_epsilon();
    else return creer_vide();
  }
  if(e->type == epsilon){
    return creer_vide();
  }
  if(e->type == vide){
    return creer_vide();
  }
}
 
int main(int argc, char *argv[])
{
  char *s = argv[1];
  char c = *argv[2];
  expr *e = NULL;
  int i = 0;
  printf("s = %s c = %c\n", s,c);
  e = E0(s, &i);
  affiche_expr(e);
  printf("\n");

  affiche_expr(residuel(e, c));
  printf("\n");

}