/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit :  librairie ABL - Gestion de representations prefixees       */
/*    Fichier :  prefbib.c                                                  */
/*                                                                          */
/*    (c) copyright 1991 Laboratoire MASI equipe CAO & VLSI                 */
/*    Tous droits reserves                                                  */
/*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
/*                                                                          */
/*    Auteur(s) :  Burgun Luc                           le : 12/12/90       */
/*                                                                          */
/*    Modifie par :   "    "                            le : 28/08/91       */
/*    Modifie par :                                     le : 07/01/92       */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include <stdio.h>
#include <ctype.h>
#include  MUT_H
#include "log200.h"

#undef MIN_OPER
#undef MAX_OPER
#define MIN_OPER 0
#define MAX_OPER 1000

/*-------------------------------------------------------------------------
gensym_abl 	: calcule un identificateur avec concatenation d'un numero.
---------------------------------------------------------------------------
retour		: un pointeur de chaine de caracteres.
---------------------------------------------------------------------------*/
char *gensym_abl(name,num)
char *name;
int num;
{
char *name1;
char number[3];
char *ret;

name1 = (char *) mbkalloc (strlen(name)+5);
(void *)strcpy(name1,name);
sprintf(number,"%d",num) ;
strcat(name1,number);
ret = namealloc(name1);
mbkfree(name1);
return(ret);
}

/*================ Gestion des erreurs ====================*/

/*------------------------------------------------------------------
  IDENT : ablError
  ------------------------------------------------------------------
  FUNCTION : verifie que expr est bien une expression. func est le nom
             la fonction appelante.
  ------------------------------------------------------------------ */

void ablError(expr,func)
chain_list *expr;
char *func;
{
int oper = OPER(expr);

if (oper < MIN_OPER || oper > MAX_OPER)
   {
   printf("\n%s: error - bad argument\n",func);
   exit(-1);
   } 
}

/*================ Creation et destruction d'ABL ====================*/


/*------------------------------------------------------------------
  IDENT : createAtom
  ------------------------------------------------------------------
  FUNCTION : cree un atome (un doublet) avec son CAR qui pointe sur
             name et son CDR egal a NULL. 
  ------------------------------------------------------------------ */

chain_list *createAtom(name)
char *name;
{
return(addchain(NULL,(void *)namealloc(name)));
}

/*------------------------------------------------------------------
  IDENT : createExpr
  ------------------------------------------------------------------
  FUNCTION : cree une tete d'expression ayant oper comme operateur. 
  ------------------------------------------------------------------ */

chain_list *createExpr(oper)
short oper;
{
	/* POUR GNU : le cast (void *)oper a ete enleve' */
if (oper >= MIN_OPER && oper <= MAX_OPER)
   return(addchain(NULL,(void *) addchain(NULL,oper)));
else
   {
   printf("\ncreateExpr: error - unknown operator %d\n",oper);
   exit(-1);
   }
}


/*------------------------------------------------------------------
  IDENT : notExpr
  ------------------------------------------------------------------
  FUNCTION : ajoute un NOT sur une expression.
  ------------------------------------------------------------------ */

chain_list *notExpr(expr)
chain_list *expr;
{
chain_list *expr1;

if (!ATOM(expr) && OPER(expr) == NOT)	/* simplification */
   {
   expr1 = CAR(CDR(expr));
   delchain(CAR(expr),CAR(expr));    /* desalloue l'operateur */
   freechain(expr);
   return(expr1);
   }
expr1 = createExpr(NOT);
addHExpr(expr1,expr);
return(expr1);
}

/*------------------------------------------------------------------
  IDENT : createBinExpr
  ------------------------------------------------------------------
  FUNCTION : creer une expression a partir de deux expressions 
	     avec fusion possible des operateurs.
  ------------------------------------------------------------------ */


chain_list *createBinExpr(oper,expr1,expr2)
short oper;
chain_list *expr1,*expr2;
{
chain_list *expr,*exprp;

if (oper < MIN_OPER || oper > MAX_OPER || oper == NOT)
   {
   printf("\ncreateBinExpr: error - bad operator %d\n",oper);
   exit(-1);
   }
if (ATOM(expr1) || OPER(expr1) != oper) /* non-compactage sur l'operateur */ 
   {
   expr = createExpr(oper);
   addHExpr(expr,expr1);
   }
else
   {
   expr = expr1;
   }
if (ATOM(expr2) || OPER(expr2) != oper) /* non-compactage sur l'operateur */ 
   {
   addHExpr(expr,expr2);
   }
else		/* Fusion de expr2 dans expr */
   {
   exprp = expr2;
   while (CDR(exprp) != NULL)
      {
      exprp = CDR(exprp);
      }
   exprp->NEXT = expr->NEXT;
   expr->NEXT = expr2->NEXT;
   expr2->NEXT = NULL;		/* desa. de la tete de expr2 */
   freeExpr(expr2);
   }
return(expr);
}

/*------------------------------------------------------------------
  IDENT : addQExpr
  ------------------------------------------------------------------
  FUNCTION : ajoute a la fin d'une expression un nouvel argument. 
  ------------------------------------------------------------------ */

void addQExpr(expr1,expr2)
chain_list *expr1,*expr2;
{

ablError(expr1,"addQExpr");

while (CDR(expr1))
   expr1 = CDR(expr1);
expr1->NEXT = addchain(NULL,(void *) expr2);
}

/*------------------------------------------------------------------
  IDENT : addHExpr
  ------------------------------------------------------------------
  FUNCTION : ajoute au debut d'une expression un nouvel argument. 
  ------------------------------------------------------------------ */

void addHExpr(expr1,expr2)
chain_list *expr1,*expr2;
{

ablError(expr1,"addHExpr");

expr1->NEXT = addchain(expr1->NEXT,(void *)expr2);
}

/*------------------------------------------------------------------
  IDENT : freeExpr
  ------------------------------------------------------------------
  FUNCTION : Desalloue l'expression jusqu'aux atomes. 
  ------------------------------------------------------------------ */

void freeExpr(expr)
chain_list *expr;
{
chain_list *pt;

if (ATOM(expr))
   freechain(expr);
else
   {
   pt = expr;
   delchain(CAR(expr),CAR(expr));    /* desalloue l'operateur */
   while((expr = CDR(expr)))           /* puis les ss-expr...   */
       freeExpr(CAR(expr)); 
   freechain(pt);
   }
} 


/*============================ Affichage ============================*/

/*------------------------------------------------------------------
  IDENT : operToChar
  ------------------------------------------------------------------
  FUNCTION : renvoie la chaine de car. correspondant a l'operateur
             oper.
  ------------------------------------------------------------------ */

char *operToChar(oper)
short oper;
{
if (oper >= MIN_OPER && oper <= MAX_OPER)
   {
   switch (oper)
      {
      case NOT  : return(namealloc("not"));
      case AND  : return(namealloc("and"));
      case OR   : return(namealloc("or"));
      case NAND : return(namealloc("nand"));
      case NOR  : return(namealloc("nor"));
      case XOR  : return(namealloc("xor"));
      case NXOR : return(namealloc("nxor"));
      case STABLE : return(namealloc("stable"));
      default   : return(namealloc("???"));
      }
   }
else
   {  
   printf("\nablError - operToChar: unknown operator %d\n",oper);
   exit(-1);
   }
}
/*------------------------------------------------------------------
  IDENT : charToOper
  ------------------------------------------------------------------
  FUNCTION : renvoie le numero d'oper. correspondant a l'ident
             name.
  ------------------------------------------------------------------ */

int charToOper(name)
char *name;
{
if (name == namealloc("not"))
   return(NOT);
if (name == namealloc("and"))
   return(AND);
if (name == namealloc("or"))
   return(OR);
if (name == namealloc("xor"))
   return(XOR);
if (name == namealloc("nand"))
   return(NAND);
if (name == namealloc("nor"))
   return(NOR);
if (name == namealloc("nxor"))
   return(NXOR);
if (name == namealloc("stable"))
   return(STABLE);
return(-1);
}

/*------------------------------------------------------------------
  IDENT : displayExpr
  ------------------------------------------------------------------
  FUNCTION : affiche l'expression a la sauce LISP --> (oper list_arg) 
  ------------------------------------------------------------------ */

void displayExprInt(expr)
chain_list *expr;
{
int oper;

if (ATOM(expr))
   printf(" %s",VALUE_ATOM(expr));
else
   {
   oper = OPER(expr);
   if (oper >= MIN_OPER && oper <= MAX_OPER)
      {
      printf(" (%s",operToChar(OPER(expr)));
      mapExpr(displayExprInt,expr);
      printf(")");
      }
   else
      {
      printf("\ndisplayExpr : error - unknown operator %d\n",oper);
      exit(-1);
      }
   }
}

void displayExpr(expr)
chain_list *expr;
{
   displayExprInt(expr);
   printf("\n");
}



/*------------------------------------------------------------------
  IDENT : displayInfExpr
  ------------------------------------------------------------------
  FUNCTION : affiche l'ABL "expr" en infixe
  ------------------------------------------------------------------ */

void displayInfExpr(expr)
chain_list *expr;
{
int oper;

if (ATOM(expr))				/* Traitement atomique */
   printf("%s",VALUE_ATOM(expr));
else					/* Traitement d'expression */
   {
   oper = OPER(expr);			/* Sauvegarde de l'operateur */
   if (oper == NOT)			/* Traitement du NOT */
      {
      printf("not ");
      displayInfExpr(CAR(CDR(expr)));
      }
   else					/* Traitement des autres operateurs */
      {
      printf("(");
      while ((expr = CDR(expr)))
         {
         displayInfExpr(CAR(expr));
         if (CDR(expr))				/* Un operateur en moins que  */
            printf(" %s ",operToChar(oper));	/* le nombre d'arguments      */
         }
      printf(")");
      }
   }
}

/*------------------------------------------------------------------
  IDENT : exprToChar
  ------------------------------------------------------------------
  FUNCTION : renvoie une chaine de caracteres correspondant a la fonction
             en mode infixe (mode = 1) ou en mode prefixe (mode = 0)
  ------------------------------------------------------------------ */

char *exprToCharInt(expr,mode,chaine,taille)
chain_list *expr;
int mode;
char *chaine;
int *taille;
{
char *oper;
int lenVA;

if (ATOM(expr))
   {
   if (*taille < strlen(chaine)+50)		/* re-allocation */
      {
      *taille = *taille + 100;
      chaine = (char *) realloc(chaine,*taille);
      }
   lenVA = strlen(VALUE_ATOM(expr));
      
   strncat(chaine,VALUE_ATOM(expr),lenVA);
   return(chaine);
   }
else
   {
   oper = operToChar(OPER(expr));

   if (mode)			/*----  infixe ----*/
      {
      if (OPER(expr) == NOT)
         {
         strncat(chaine,"not ",4);
         chaine = exprToCharInt(CAR(CDR(expr)),mode,chaine,taille);
         return(chaine);
         }
      else
         {
         strncat(chaine,"(",1);
         while ((expr = CDR(expr)))
            {
            chaine = exprToCharInt(CAR(expr),mode,chaine,taille);
            if (CDR(expr))
               {
               strncat(chaine," ",1);
               strcat(chaine,oper);
               strncat(chaine," ",1);
               }
            }
         strncat(chaine,")",1);
         return(chaine);
         }
      }
   else				/*----- prefixe -----*/
      {
      int lenOPER = strlen(oper);
      strncat(chaine,"(",1);
      strncat(chaine,oper,lenOPER);
      while ((expr = CDR(expr)))
         {
         strncat(chaine," ",1);
         chaine = exprToCharInt(CAR(expr),mode,chaine,taille);
         }
      strncat(chaine,")",1);
      return(chaine);
      }
   }
}

char *exprToChar(expr,mode)
chain_list *expr;
int mode;
{
char *chaine;
int taille;

taille = 100;
chaine = (char *) mbkalloc(100);
chaine[0]='\0';
return(exprToCharInt(expr,mode,chaine,&taille));
}


/*------------------------------------------------------------------
  IDENT : identExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie une chaine de caracteres correspondant a un nom
	     d'expression au variable pres. 
  ------------------------------------------------------------------ */

char *identExprInt(expr,chaine,taille)
chain_list *expr;
char *chaine;
int *taille;
{

if (ATOM(expr))
   {
   return(chaine);
   }
else
   {
   chain_list *expr1;
   char arite[3];
   int oper = OPER(expr);

   switch (oper)
      {
      case NOT  : strncat(chaine,"n",1);
                  break;
      case AND  : strncat(chaine,"a",1);
		  break;
      case OR   : strncat(chaine,"o",1);
		  break;
      case NAND : strncat(chaine,"na",2);
		  break;
      case NOR  : strncat(chaine,"no",2);
		  break;
      case XOR  : strncat(chaine,"x",1);
		  break;
      case NXOR : strncat(chaine,"nx",2);
		  break;
      default   : strncat(chaine,"???",3);
      }
   expr1 = expr; 
   while ((expr = CDR(expr)))
         {
         chaine = identExprInt(CAR(expr),chaine,taille);
         }
   if (oper != NOT)
      {
      sprintf(arite,"%d",lengthExpr(expr1)) ;
      strcat(chaine,arite);
      }
   return(chaine);
   }
}


char *identExpr(expr)
chain_list *expr;
{
char *chaine,*bidon;
int taille,i;
chain_list *expr1;
int flag_alloc = 0;

taille = 100;

		/* normalisation */

flatArityExpr(expr);
if (searchOperExpr(expr,NOT))
   {
   if (!searchOperExpr(expr,XOR))
      {
      flag_alloc = 1;
      expr1 = flatPolarityExpr(expr,1);
      if (searchOperExpr(expr1,NOT))
         {
         expr = notExpr(flatPolarityExpr(expr1,0) );
         freeExpr(expr1);
         }
      else
         {
         expr = expr1; 
         }
      }
   }
   
if (profExpr(expr) == 1)
   {
   chaine = gensym_abl(operToChar(OPER(expr)),lengthExpr(expr));
   }
else
   if (profExpr(expr) == 2 && OPER(expr) == NOT)
      {
      bidon = (char *) mbkalloc(taille);
      bidon[0]='n';
      bidon[1]='\0';
      strcat(bidon,operToChar(OPER(CADR(expr))));
      chaine = gensym_abl(bidon,lengthExpr(CADR(expr)));
#ifndef LEO
   mbkfree(bidon);
#endif
      }
   else
      {
      bidon = (char *) mbkalloc(taille);
      bidon[0] = '\0';
      bidon = identExprInt(expr,bidon,&taille);
      for(i = strlen(bidon)-1; bidon[i] == '_'; i--)
         bidon[i] = '\0';
      chaine = namealloc(bidon);
#ifndef LEO
   mbkfree(bidon);
#endif
      }
if (flag_alloc)
   freeExpr(expr);
return(chaine);
}

/*------------------------------------------------------------------
  IDENT : profExpr
  ------------------------------------------------------------------
  FUNCTION : calcule la profondeur d'une expression.
  ------------------------------------------------------------------*/

int profExpr(expr)
chain_list *expr;
{
if (ATOM(expr))
   return(0);
else
   {
   int max=0,profCar;

   while ((expr = CDR(expr)))
      {
      profCar = profExpr(CAR(expr));
      if (profCar >max)
         max = profCar;
      }
   return(++max);
   }
}
/*------------------------------------------------------------------
  IDENT : profAOExpr
  ------------------------------------------------------------------
  FUNCTION : calcule la profondeur d'une expression sans tenir compte
  des inverseurs.
  ------------------------------------------------------------------*/

int profAOExpr(expr)
chain_list *expr;
{
if (ATOM(expr))
   return(0);
else
   {
   int max=0,profCar,oper=OPER(expr);

   while ((expr = CDR(expr)))
      {
      profCar = profAOExpr(CAR(expr));
      if (profCar >max)
         max = profCar;
      }
   if (oper == NOT) return max;
   return(++max);
   }
}

/*======================= Les fonctionnelles ========================*/


/*------------------------------------------------------------------
  IDENT : mapCarExpr
  ------------------------------------------------------------------
  FUNCTION : applique la fonction func sur l'expression expr et
             renvoie une expression ayant oper comme operateur et 
             ayant pour ss-expr. le resultat de l'application de 
             func sur les ss-expr. de expr.
  ------------------------------------------------------------------*/

chain_list *mapCarExpr(func,oper,expr)
chain_list *(*func)();
short oper;
chain_list *expr;
{
chain_list *pt;

pt = createExpr(oper);
while ((expr = CDR(expr)))
   addQExpr(pt,(*func)(CAR(expr)));
return(pt);
}


/*------------------------------------------------------------------
  IDENT : mapExpr
  ------------------------------------------------------------------
  FUNCTION : applique la fonction func sur l'expression expr.
             func doit renvoye un void et prendre comme argument un 
             pointeur de chain_list.
  ------------------------------------------------------------------*/

void mapExpr(func,expr)
void (*func)();
chain_list *expr;
{
while ((expr = CDR(expr)))
   (*func)(CAR(expr));
}


/*------------------------------------------------------------------
  IDENT : anyExpr
  ------------------------------------------------------------------
  FUNCTION : applique la fonction func sur l'expression expr.
             renvoie 1 s'il y a eu au moins un appel de func qui a
             renvoye 1. (OU  logique)
  ------------------------------------------------------------------*/

int anyExpr(func,expr)
int (*func)();
chain_list *expr;
{
while ((expr = CDR(expr)))
   if ((*func) (CAR(expr)))
      return(1);
return(0);
}

/*------------------------------------------------------------------
  IDENT : EveryExpr
  ------------------------------------------------------------------
  FUNCTION : applique la fonction func sur l'expression expr.
             renvoie 1 si tout les appels de func ont renvoye 1.
            (ET  logique)
  ------------------------------------------------------------------*/

int everyExpr(func,expr)
int (*func)();
chain_list *expr;
{
while ((expr = CDR(expr)))
   if (!((*func) (CAR(expr))))
      return(0);
return(1);
}

/*====================== Manipulations d'ABL =========================*/

/*------------------------------------------------------------------
  IDENT : searchOperExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie 1 si oper existe dans expr, 0 sinon.
  ------------------------------------------------------------------*/

int searchOperExpr(expr,oper)
chain_list *expr;
int oper;
{
if (ATOM(expr))
   return(0);
else
   if (OPER(expr) == oper)
      return(1);
   else
      {
      while ((expr = CDR(expr)))
         if (searchOperExpr(CAR(expr),oper) == 1)
            return(1);
      return(0);
      }
}

/*------------------------------------------------------------------
  IDENT : searchExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie 1 si name existe dans expr, 0 sinon.
  ------------------------------------------------------------------*/

int searchExpr(expr,name)
chain_list *expr;
char *name;
{
short searchExprLow();

name = namealloc(name);
return(searchExprLow(expr,name));
}

short searchExprLow(expr,name)
chain_list *expr;
char *name;
{
if (ATOM(expr))
   if (name == VALUE_ATOM(expr))
      return(1);
   else
      return(0);
else
   {
   while ((expr = CDR(expr)))
      if (searchExprLow(CAR(expr),name))
         return(1);
   return(0);
   }
}

/*------------------------------------------------------------------
  IDENT : equalExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie 1 si expr1 = expr2, 0 sinon.
  ------------------------------------------------------------------*/

int equalExpr(expr1,expr2)
chain_list *expr1,*expr2;
{
if (ATOM(expr1))
   if (ATOM(expr2) && (CAR(expr1) == CAR(expr2)))
      return(1);
   else
      return(0);
if (ATOM(expr2))
   return(0);
else
   {
   if (OPER(expr1) != OPER(expr2))   	/* egalite des operateurs */
      return(0);
   expr1 = CDR(expr1);
   expr2 = CDR(expr2);
   while (expr1 && expr2)
      {
      if (!(equalExpr(CAR(expr1),CAR(expr2))))
         return(0);
      expr1 = CDR(expr1);
      expr2 = CDR(expr2);
      }
   if (expr2 || expr1)
      return(0); 
   else
      return(1);
   }
}

/*------------------------------------------------------------------
  IDENT : equalVarExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie 1 si expr1 = expr2, 0 sinon.
  ------------------------------------------------------------------*/

int equalVarExpr(expr1,expr2)
chain_list *expr1,*expr2;
{
if (ATOM(expr1))
   {
   if (ATOM(expr2))
      return(1);
   else
      return(0);
   }
if (ATOM(expr2))
   return(0);
else
   {
   if (OPER(expr1) != OPER(expr2))   	/* egalite des operateurs */
      return(0);
   expr1 = CDR(expr1);
   expr2 = CDR(expr2);
   while (expr1 && expr2)
      {
      if (!(equalVarExpr(CAR(expr1),CAR(expr2))))
         return(0);
      expr1 = CDR(expr1);
      expr2 = CDR(expr2);
      }
   if (expr2 || expr1)
      return(0); 
   else
      return(1);
   }
}

/*------------------------------------------------------------------
  IDENT : lengthExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie la taille de l'expression au premier niveau.
             (en fait l'arite de l'operateur)
  ------------------------------------------------------------------*/

int lengthExpr(expr)
chain_list *expr;
{
if (ATOM(expr))
   return(1);
else
   {
   int cpt = 0;
   while ((expr = CDR(expr))) cpt++;
   return(cpt);
   }
}
/*------------------------------------------------------------------
  IDENT : numberOperBinExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie le nombre d'operateurs binaires (equivalent) 
             d'une expression.
  ------------------------------------------------------------------*/

int numberOperBinExpr(expr)
chain_list *expr;
{
if (ATOM(expr))
   return(0);
else
   {
   int cpt = -1;
   if (OPER(expr) == NOT)
      return (numberOperBinExpr(CADR(expr)));
   while((expr = CDR(expr)))
       cpt = 1 + cpt + numberOperBinExpr(CAR(expr));
   return(cpt);
   }
}


/*------------------------------------------------------------------
  IDENT : numberAtomExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie le nombre d'atomes de l'expression.
  ------------------------------------------------------------------*/

int numberAtomExpr(expr)
chain_list *expr;
{
if (ATOM(expr))
   return(1);
else
   {
   int cpt = 0;
   while((expr = CDR(expr)))
       cpt = cpt + numberAtomExpr(CAR(expr));
   return(cpt);
   }
}

/*------------------------------------------------------------------
  IDENT : copyExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie une expression qui correspond a une recopie de
             expr (avec l'arite).
  ------------------------------------------------------------------*/

chain_list *copyExpr(expr)
chain_list *expr;
{
if (ATOM(expr))
   return(addchain(NULL,expr->DATA));
else
   {
   chain_list *auxExpr;
   chain_list *oldExpr = expr;
   chain_list *expr1;

   auxExpr = createExpr(OPER(expr));
   expr1 = auxExpr;

   while ((expr = CDR(expr)))
      {

		/* on optimise a fond la recopie de la dorsale */

      expr1->NEXT = addchain(NULL,(void *) copyExpr(CAR(expr)));
      expr1 = CDR(expr1);

   		/* remplace : addQExpr(auxExpr,copyExpr(CAR(expr))); */
      }

	/* on sauvegarde la poubelle */

   ((chain_list *)auxExpr->DATA)->NEXT = CDR(CAR(oldExpr)); 
   return(auxExpr);
   }
}
/*------------------------------------------------------------------
  IDENT : substPhyExpr
  ------------------------------------------------------------------
  FUNCTION : substitue toutes les occurences de "name" par
             l'expression expr1.
  ------------------------------------------------------------------*/

void substPhyExpr(expr1,name,expr2)
chain_list *expr1;
char *name;
chain_list *expr2;

{
if (!ATOM(expr1))
   {
   while ((expr1 = CDR(expr1)))
      if (ATOM(CAR(expr1)))
         {
         if (!strcmp(name,VALUE_ATOM(CAR(expr1))))
            {
            freechain(CAR(expr1));
            expr1->DATA = (void *)copyExpr(expr2);
            }
         }
      else
         substPhyExpr(CAR(expr1),name,expr2);
   }
}

/*------------------------------------------------------------------
  IDENT : substExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie une expression dans laquelle on a substitue 
	     toutes les occurences de "name" par l'expression expr2.
  ------------------------------------------------------------------*/

chain_list *substExpr(expr1,name,expr2)
chain_list *expr1;
char *name;
chain_list *expr2;

{
if (ATOM(expr1))
   if (!strcmp(name,VALUE_ATOM(expr1)))
      return(copyExpr(expr2));
   else
      return(copyExpr(expr1));
else
   {
   chain_list *res;
   res = createExpr(OPER(expr1));
   while ((expr1 = CDR(expr1)))
      addQExpr(res,substExpr(CAR(expr1),name,expr2));
   return(res);
   }
}


/*------------------------------------------------------------------
  IDENT : devXorExpr
  ------------------------------------------------------------------
  FUNCTION : developpe recursivement les XOR dans une expression. 
             a xor b = ((not a) and b) or (a and (not b))
  ------------------------------------------------------------------*/

chain_list *devXorExpr(expr)
chain_list *expr;
{
if (ATOM(expr))
   return(copyExpr(expr));
else
   {
   if (OPER(expr) != XOR)
      return(mapCarExpr(devXorExpr,OPER(expr),expr));
   else
      if (lengthExpr(expr) == 2)
         {
         chain_list *dev,*ret;

         dev = devXor2Expr(expr);
         ret = devXorExpr(dev);
         freeExpr(dev);
         return(ret);
         }
      else
		/* XOR N>2 */
        {
        chain_list *xor,*dev,*inter;

        xor = createExpr(XOR);
        addHExpr(xor,copyExpr(CADR(expr))); 

		/* elimination du premier arg dans expr */

        inter = createExpr(XOR);
        expr = CDR(expr);
        while ((expr = CDR(expr)))
           addHExpr(inter,copyExpr(CAR(expr)));

        dev = devXorExpr(inter);	/* on developpe expr */
        freeExpr(inter);

        addQExpr(xor,dev);
        dev = devXor2Expr(xor);
        freeExpr(xor);
        return(dev);
        } 
   }
}

/*------------------------------------------------------------------
  IDENT : devXorExpr
  ------------------------------------------------------------------
  FUNCTION : developpe un XOR 2
             a xor b = ((not a) and b) or (a and (not b))
  ------------------------------------------------------------------*/

chain_list *devXor2Expr(expr)
chain_list *expr;
{
if (ATOM(expr) || OPER(expr) != XOR || lengthExpr(expr) > 2)
   return(copyExpr(expr));
else
   {
   chain_list *ret;
   chain_list *and1,*and2;
   chain_list *a,*b;

   a = CADR(expr);		/* premier argument */
   b = CADR(CDR(expr)); 	/* deuxieme argument */
   ret = createExpr(OR);
   and1 = createExpr(AND);
   and2 = createExpr(AND);
   addQExpr(and1,copyExpr(a));
   addQExpr(and2,copyExpr(b));
   
   addQExpr(and1,notExpr(copyExpr(b)));
   addQExpr(and2,notExpr(copyExpr(a)));
   addQExpr(ret,and2);
   addQExpr(ret,and1);
   return(ret);
   }
}


/*------------------------------------------------------------------
  IDENT : flatPolarityExpr
  ------------------------------------------------------------------
  FUNCTION : Reporte sur les entrees primaires (atomes) la negation
             par applications successives des lois de Morgan et de
             simplifications de l'algebre de Boole.
             Si le signe est egal a 0 a l'appel, on obtient un
             report sur la fonction inverse.
  ------------------------------------------------------------------ */

chain_list *flatPolarityExpr(expr,signe)
chain_list *expr;
int signe;
{
short oper;
chain_list *pt;

if (ATOM(expr))
   if (signe)
      return(createAtom(VALUE_ATOM(expr)));
   else
      {
      pt = createExpr(NOT);
      addQExpr(pt,createAtom(VALUE_ATOM(expr)));
      return(pt);
      }
else
   {
   oper = OPER(expr);
   if (oper == NOT)		/* operateur NOT */
      {
      expr = CADR(expr); 
      if (signe)
         return(flatPolarityExpr(expr,0));
      else
         return(flatPolarityExpr(expr,1));
      }
   else
      {
      if (oper == OR || oper == AND)
         {
         if (signe)		/* aucun changement a ce niveau */
            pt = createExpr(oper);
         else			/* application des lois de Morgan */
            if (oper == AND)
               pt = createExpr(OR);
            else
               pt = createExpr(AND);
         while ((expr = CDR(expr)))
            addQExpr(pt,flatPolarityExpr(CAR(expr),signe));
         return(pt);
         }
      if (oper == NOR || oper == NAND)
         {
         pt = copyExpr(expr);
         if (OPER(expr) == NOR)
            changeOperExpr(pt,OR);
         else
            changeOperExpr(pt,AND);
         if (signe)
            expr = flatPolarityExpr(pt,0);
         else
            expr = flatPolarityExpr(pt,1);
         freeExpr(pt);
         return(expr);
         }
      printf("flatPolarityExpr: error - unknown operator %s\n",operToChar(oper));
      exit(-1);
      }
   }
}

/*------------------------------------------------------------------
  IDENT : flatArityExpr
  ------------------------------------------------------------------
  FUNCTION : Ecrase une expression par elimination des operateurs redondants.  
  ------------------------------------------------------------------ */

void flatArityExpr(expr)
chain_list *expr;
{
int oper;
chain_list *expr1,*expr2,*exprBefore;

if (!ATOM(expr))
   {
   oper = OPER(expr);
   if (oper == NOT || oper == STABLE)
      flatArityExpr(CAR(CDR(expr)));
   else
      {
      expr1 = expr;
      exprBefore = expr;
      while ((expr1 = CDR(expr1)))
         {
         expr2 = CAR(expr1);
         if (!ATOM(expr2))
            {
            if (oper == OPER(expr2))		/* detection OK */
               {
               exprBefore->NEXT = CDR(expr2);
               while (CDR(expr2))
                  expr2 = CDR(expr2);
               CDR(expr2) = CDR(expr1); 

               CDR(expr1) = NULL;
               expr2 = CAR(expr1);
               CDR(expr2) = NULL ;
               freechain(expr1);
               freechain(expr2);
               expr1 = exprBefore;
               }
            else
               {
               flatArityExpr(expr2);  
               exprBefore = CDR(exprBefore);
               }
            }
         else
            exprBefore = CDR(exprBefore);
         }
      }
   }
}
/*------------------------------------------------------------------
  IDENT : supportChain_listExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie le support d'une expression dans une liste chainee.
             (1 seule occurence par variable).
  ------------------------------------------------------------------ */

void supportChain_listExprInt(expr,ppCL)
chain_list *expr;
chain_list **ppCL;
{
if (ATOM(expr))
   {
   chain_list *pCL = *ppCL;
   if (strcmp(VALUE_ATOM(expr),"'d'") &&
       strcmp(VALUE_ATOM(expr),"'1'") &&
       strcmp(VALUE_ATOM(expr),"'0'"))
      {

      while (pCL)			/* recherche occurence */
         {
         if ((char *)pCL->DATA == VALUE_ATOM(expr))
            return;
         pCL = pCL->NEXT;
         }
      *ppCL = addchain(*ppCL,(void *)VALUE_ATOM(expr));
      }
   }
else
   {
   while ((expr = CDR(expr)))
      supportChain_listExprInt(CAR(expr),ppCL);
   }
}

chain_list *supportChain_listExpr(expr)
chain_list *expr;
{
chain_list **ppCL;
chain_list *res;

ppCL = (chain_list **) mbkalloc (sizeof(chain_list *));
*ppCL = NULL;
supportChain_listExprInt(expr,ppCL);
res = reverse(*ppCL);
mbkfree(ppCL);
return(res);
}

/*------------------------------------------------------------------
  IDENT : supportPtype_listExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie le support d'une expression dans une liste typee.
             (1 seule occurence par variable).
  ------------------------------------------------------------------ */

void supportPtype_listExprInt(expr,ppCL)
chain_list *expr;
ptype_list **ppCL;
{
if (ATOM(expr))
   {
   ptype_list *pCL = *ppCL;
   if (strcmp(VALUE_ATOM(expr),"'d'") &&
       strcmp(VALUE_ATOM(expr),"'1'") &&
       strcmp(VALUE_ATOM(expr),"'0'"))
      {
      while (pCL)			/* recherche occurence */
         {
         if ((char *)pCL->DATA == VALUE_ATOM(expr))
            return;
         pCL = pCL->NEXT;
         }
      *ppCL = addptype(*ppCL,0,(void *)VALUE_ATOM(expr));
      }
   }
else
   {
   while ((expr = CDR(expr)))
      supportPtype_listExprInt(CAR(expr),ppCL);
   }
}

ptype_list *supportPtype_listExpr(expr)
chain_list *expr;
{
ptype_list **ppCL;
ptype_list *res;

ppCL = (ptype_list **) mbkalloc (sizeof(ptype_list *));
*ppCL = NULL;
supportPtype_listExprInt(expr,ppCL);
res = (ptype_list *) reverse((chain_list*) *ppCL);
mbkfree(ppCL);
return(res);
}

/*------------------------------------------------------------------
  IDENT : maxExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie le max des arguments d'une expression avec une
  fonction de comparaison func renvoyant un int.
  ------------------------------------------------------------------ */

chain_list *maxExpr(expr,func)
chain_list *expr;
int (*func)();
{
chain_list *expr1;

expr = CDR(expr);
expr1 = expr;
while ((expr = CDR(expr)))
   if ((*func) (CAR(expr)) > (*func)(CAR(expr1)))
      expr1 = expr;
return(CAR(expr1));
}

/*------------------------------------------------------------------
  IDENT : minExpr
  ------------------------------------------------------------------
  FUNCTION : renvoie le min des arguments d'une expression avec une
  fonction de comparaison func renvoyant un int.
  ------------------------------------------------------------------ */

chain_list *minExpr(expr,func)
chain_list *expr;
int (*func)();
{
chain_list *expr1;

expr = CDR(expr);
expr1 = expr;
while ((expr = CDR(expr)))
   if ((*func) (CAR(expr)) < (*func)(CAR(expr1)))
      expr1 = expr;
return(CAR(expr1));
}

/*------------------------------------------------------------------
  IDENT : sortExpr
  ------------------------------------------------------------------
  FUNCTION : trie les arguments d'une expression a partir d'une fonction
  func renvoyant un int. 
            direction = 1 croissant  ;  direction = 0 decroissant
  ------------------------------------------------------------------ */

void sortExpr(expr,func,direction)
chain_list *expr;
int (*func)();
int direction;
{
chain_list *expr1;
int okPermu = 1;

if (!ATOM(expr))		/* ce n'est pas un atome */
   {
   while (okPermu)
      {
      expr1 = CDR(expr);
      okPermu = 0;
      while (CDR(expr1))
         {
         if ((direction == 1 && 
             ((*func) CAR(expr1) > (*func) CADR(expr1))) ||
             (direction == 0 &&
             ((*func) CAR(expr1) < (*func) CADR(expr1))))
            {
            chain_list *permu;

            permu = CAR(expr1);
            expr1->DATA = (void *)CADR(expr1);
            (expr1->NEXT)->DATA = (void *)permu;
            okPermu = 1;
            }
         expr1 = CDR(expr1);
         }
      }
   }
}

/*------------------------------------------------------------------
  IDENT : normExpr
  ------------------------------------------------------------------
  FUNCTION : normalise une expression a tous les niveaux
		variable = pointeur d'allocation
		expression = numero d'operateur. 
             ex : (and a (xor w g) b (or x f) (or e g o) (xor t h k))
                --> (and (or x f) (or e o g) (xor g w) (xor t h k) b a)
  ------------------------------------------------------------------ */

int funcNormExpr(expr)
chain_list *expr;
{
if (ATOM(expr))
   return ((int) VALUE_ATOM(expr));
else
   if (OPER(expr) == NOT)
      if (ATOM(CADR(expr)))
         return(NOT*100 + 10);
      else
         return(NOT*100 + OPER(CADR(expr)));
   return(OPER(expr)*100 + lengthExpr(expr));
}

void normExpr(expr)
chain_list *expr;
{
if (!ATOM(expr))
   {
   sortExpr(expr,funcNormExpr,1);
   while ((expr = CDR(expr)))
      normExpr(CAR(expr));
   }  
}


/*------------------------------------------------------------------------------
deleteNumExpr 	: elimine le i-eme element de expr.
                  le premier argument commence a la place 0.
------------------------------------------------------
parametres  	: un ABL et une place. 
-------------------------------------------------------
return 		: rien. 
------------------------------------------------------------------------------*/
void deleteNumExpr(expr,i)
chain_list *expr;
int i;
{
int co=0;
chain_list *e = expr,*pt;

if (lengthExpr(expr) <= i)
   {
   printf("deleteNumExpr : error - index %d out of bound for \n",i);
   displayExpr(e);
   exit(-1);
   }

pt = expr;
while ((i <= co) && (expr = CDR(expr)))
   {
   if (i == co)
      {
      CDR(pt) = CDR(expr);
      CDR(expr) = NULL;		/*desallocation du i-eme arg */
      freeExpr(CAR(expr));
      freechain(expr); 
      return;
      }
   else
      pt = CDR(pt);
   co++;
   }
}

/*------------------------------------------------------------------------------
searchNumExpr 	: renvoie le i-eme element de expr.
                  le premier argument commence a la place 0.
------------------------------------------------------
parametres  	: un ABL et une place. 
-------------------------------------------------------
return 		: un chain_list * 
------------------------------------------------------------------------------*/
chain_list *searchNumExpr(expr,i)
chain_list *expr;
int i;
{
int co=0;
chain_list *e = expr;

while ((expr = CDR(expr)))
   {
   if (i == co) return(CAR(expr));
   co++;
   }
printf("searchNumExpr : error - index %d out of bound for \n",i);
displayExpr(e);
exit(-1);
}

/*------------------------------------------------------------------------------
numberOccExpr 	: renvoie le nombre d'occurences d'une variable dans expr. 
------------------------------------------------------
parametres  	: un ABL et une variable. 
-------------------------------------------------------
return 		: un int. 
------------------------------------------------------------------------------*/
int numberOccExpr(exp,name)
chain_list *exp;
char *name;

{
if (ATOM(exp))
   {
   if ((int) name == (int)VALUE_ATOM(exp))
	return 1;
   else
        return 0;
   }
else
   {
   int cpt = 0;

   while(exp = CDR(exp))
	cpt += numberOccExpr(CAR(exp),name);
   return cpt;
   }
}

/*------------------------------------------------------------------------------
changeOperExpr 	: change l'operateur d'une expression 
------------------------------------------------------
parametres  	: un ABL
-------------------------------------------------------
return 		: un void. 
------------------------------------------------------------------------------*/

void changeOperExpr(expr,oper)
chain_list *expr;
short oper;
{
int op = (int)oper ;

if (ATOM(expr))
   {
   printf("changeOperExpr : error - atomic expression\n");
   exit(-1);
   }
else
   {
   expr = CAR(expr);
   expr->DATA = (char *) op;
   }
}

/*------------------------------------------------------------------------------
simplif10Expr 	: simplifie une expression en eliminant les constantes 0 et 1. 
------------------------------------------------------
parametres  	: un ABL
-------------------------------------------------------
return 		: un ABL. 
------------------------------------------------------------------------------*/

chain_list *simplif10Expr(expr)
chain_list *expr;
{
if (ATOM(expr))
   {
   return (copyExpr(expr));
   }
else
   {
   short oper = OPER(expr);
   chain_list *auxExpr = createExpr(oper),*args,*res;
   int cpt1 = 0;

   for(args = CDR(expr);args;args = CDR(args))
	   {
	   res = simplif10Expr(CAR(args));
	   if (!ATOM(res))
		{
                if (oper == STABLE)
                   {
                   addQExpr(auxExpr,res);
                   return auxExpr;
                   }
			/* simplif (not (not a)) -> a */

		if ((oper == NOT) && (OPER(res) == NOT))
                   {
                   freeExpr(auxExpr);
		   return notExpr(res);
                   }
		else
		   addQExpr(auxExpr,res);
		}
	   else
		{
		switch(oper)
		    {
		    case NOT  :
			if (!strcmp(VALUE_ATOM(res),"'0'"))
                           	{
				freeExpr(res);
	   	   		return createAtom("'1'");
				}
			if (!strcmp(VALUE_ATOM(res),"'1'"))
                           	{
				freeExpr(res);
	   	   		return createAtom("'0'");
				}
		   	addQExpr(auxExpr,res);
                        return auxExpr;
			break;

		    case STABLE  :
		   	addQExpr(auxExpr,res);
                        return auxExpr;
			break;

		    case AND  :
			if (!strcmp(VALUE_ATOM(res),"'0'"))
                           	{
				freeExpr(res);
	   	   		return createAtom("'0'");
				}
			if (strcmp(VALUE_ATOM(res),"'1'"))
		   		addQExpr(auxExpr,res);
			break;
		    case NAND :
			if (!strcmp(VALUE_ATOM(res),"'0'"))
                           	{
				freeExpr(res);
	   	   		return createAtom("'1'");
				}
			if (strcmp(VALUE_ATOM(res),"'1'"))
		   		addQExpr(auxExpr,res);
			break;
		    case OR   :
			if (!strcmp(VALUE_ATOM(res),"'1'"))
                           	{
				freeExpr(res);
	   	   		return createAtom("'1'");
				}
			if (strcmp(VALUE_ATOM(res),"'0'"))
		   		addQExpr(auxExpr,res);
			break;
		    case NOR  :
			if (!strcmp(VALUE_ATOM(res),"'1'"))
                           	{
				freeExpr(res);
	   	   		return createAtom("'0'");
				}
			if (strcmp(VALUE_ATOM(res),"'0'"))
		   		addQExpr(auxExpr,res);
			break;
		    case XOR  :
			if (!strcmp(VALUE_ATOM(res),"'1'"))
			   cpt1++;
			else
			if (strcmp(VALUE_ATOM(res),"'0'"))
		   		addQExpr(auxExpr,res);
			break;
		    case NXOR  :
			if (!strcmp(VALUE_ATOM(res),"'1'"))
			   cpt1++;
			else
			if (strcmp(VALUE_ATOM(res),"'0'"))
		   		addQExpr(auxExpr,res);
			break;
		    }
		}
	}
			/* cas des XOR */

	if ( ((cpt1 % 2) == 1) && CDR(auxExpr) )
	   {
           if (lengthExpr(auxExpr) < 2)
              {
              if (!CDR(auxExpr))
		 return createAtom("'1'");
	      else   
		 changeOperExpr(auxExpr,NOT);
              }
           else
              {
	      chain_list *aux = createExpr(NOT);
              addQExpr(aux,auxExpr);
	      auxExpr = aux; 
              }
	   }
			/* expression normale */

	if ((lengthExpr(auxExpr) >1) || (OPER(auxExpr) == NOT))
	   return auxExpr;

			/* traitement pas d'argument */
        if (!CDR(auxExpr))
	   {
 	   freeExpr(auxExpr);
	   if ( (oper == NAND) || (oper == OR) )
		return createAtom("'0'");
	   if ( (oper == AND) || (oper == NOR) )
	   	return createAtom("'1'");
	   if (oper == XOR)
		if ((cpt1 % 2) == 1)
		   return createAtom("'1'");
		else
		   return createAtom("'0'");
	   if (oper == NXOR)
		if ((cpt1 % 2) == 1)
		   return createAtom("'0'");
		else
		   return createAtom("'1'");
	   }
			/* traitement 1 seul argument */

	   if ( (oper == AND) || (oper == OR) )
		return CADR(auxExpr);
	   if ( (oper == NAND) || (oper == NOR) )
		{
		changeOperExpr(auxExpr,NOT);
	        return auxExpr;
		}
	   if (oper == XOR)
		if ((cpt1 % 2) == 1)
		{
		changeOperExpr(auxExpr,NOT);
	        return auxExpr;
		}
		else
		   return CADR(auxExpr);
	   if (oper == NXOR)
		if ((cpt1 % 2) == 1)
		   return CADR(auxExpr);
		else
		{
		changeOperExpr(auxExpr,NOT);
	        return auxExpr;
		}
   }
}
/*------------------------------------------------------------------------------
simplifNotExpr 	: simplifie une expression en appliquant (not (not a)) --> a 
------------------------------------------------------
parametres  	: un ABL et une variable. 
-------------------------------------------------------
return 		: un int. 
------------------------------------------------------------------------------*/
chain_list *simplifNotExpr(exp)
chain_list *exp;

{
if (ATOM(exp))
   return copyExpr(exp);
if (OPER(exp) == NOT)
   {
   if (!ATOM(CADR(exp)) && OPER(CADR(exp)) == NOT)	/* (not (not a)) */
      return(simplifNotExpr(CADR(CADR(exp))));
   else
      {
      chain_list *expr;
      expr = createExpr(NOT);
      addQExpr(expr,simplifNotExpr(CADR(exp)));
      return expr;
      }
   }
else
	{
        return (mapCarExpr(simplifNotExpr,OPER(exp),exp));
	}
}

/*------------------------------------------------------------------------------
charToExpr :	analyse une chaine de caracteres decrivant une
                equation logique et remplit l'expression de retour. 
-------------------------------------------------------
parametres :	char.
-------------------------------------------------------
return :	expr.
------------------------------------------------------------------------------*/


chain_list *charToExprInt(stringExpr,cptCar)
char *stringExpr;
int *cptCar;
{
char *tokOper;
char *tok;
char *tokenExpr();
chain_list *expr;

tok = tokenExpr(stringExpr,cptCar);
if (!tok)
   {
   printf("charToExpr : error - bad string to convert\n");
   printf("%s\n",stringExpr);
   exit(-1);
   }

if(strcmp(tok,"("))		/* noeud terminal direct */
  {
  return createAtom(tok);
  }

free(tok) ;

tokOper = tokenExpr(stringExpr,cptCar);
if (!tokOper)
   {
   printf("charToExpr : error - bad string to convert\n");
   printf("%s\n",stringExpr);
   exit(-1);
   }
switch(*tokOper)
	{
	case 'o' :
	        expr = createExpr(OR);	
		break ;
	case 'a' :
	        expr = createExpr(AND);	
		break ;
	case 'x' :
	        expr = createExpr(XOR);	
		break ;
	case 's' :
	        expr = createExpr(STABLE);	
		break ;
	case 'n' :
		switch(*(tokOper + 2))
			{
			case 't' :
	                        expr = createExpr(NOT);	
				break ;
			case 'r' :
	                        expr = createExpr(NOR);	
				break ;
			case 'n' :
	                        expr = createExpr(NAND);	
				break ;
			case 'o' :
	                        expr = createExpr(NXOR);	
				break ;
			default :
				printf("charToExpr : error - bad operator %s\n",tokOper);
				exit(-1);
			}
		break ;
	default :
	  printf("charToExpr : error - bad operator %s\n",tokOper);
	  exit(-1);
	}
free(tokOper) ;

tok = tokenExpr(stringExpr,cptCar);   /* lecture des operandes */
if (!tok)
   {
   printf("charToExpr : error - bad string to convert\n");
   printf("%s\n",stringExpr);
   exit(-1);
   }

do
   {
          /* traitement des elements terminaux*/

   if (strcmp(tok,"("))
      {
      addQExpr(expr,createAtom(tok));
      free(tok);
      }
   else	
      {
	/* traitement des sous-expressions */

      free(tok);
      *cptCar = *cptCar - 1;	/*compteur revient sur "(" */

      addQExpr(expr,charToExprInt(stringExpr,cptCar));
      }	

   tok = tokenExpr(stringExpr,cptCar);
   if (!tok)
      {
      printf("charToExpr : error - bad string to convert\n");
      printf("%s\n",stringExpr);
      exit(-1);
      }
   }
while (strcmp(tok,")"));
free(tok) ;

      /* on applique maintenant l'operateur */

return(expr);
}

chain_list *charToExpr(stringExpr)
char *stringExpr;
{
int cptCar = 0;
return(charToExprInt(stringExpr,&cptCar));
}

/*------------------------------------------------------------------------------
tokenExpr :		cherche les tokenExprs.
-------------------------------------------------------
parametres :	rien.
-------------------------------------------------------
return :	(, ), ou une chaine de caractere.
------------------------------------------------------------------------------*/
char *tokenExpr(stringExpr,cptCar)
char *stringExpr;
int *cptCar;
{
char *tok;
int i;
int compteur = *cptCar;

for (; isspace(stringExpr[compteur]) ; compteur++);	/* suppression ds blancs */

if (stringExpr[compteur] == '\0')	/* probleme ... */
    return (NULL);

i = compteur;

		/* on avance jusqu'au prochain tokenExpr */

for (;isspace(stringExpr[i]) == 0 && strncmp(stringExpr+i,")",1) != 0 && strncmp(stringExpr+i,"(",1) != 0 ; i++);

	/* parenthese ouvrante ou fermante */

if(!strncmp(stringExpr+compteur,"(",1) || !strncmp(stringExpr+compteur,")",1))
	{
	tok = (char *)malloc(2);
	strncpy(tok, stringExpr + i,1);
	tok[1] = '\0';
	compteur++;
        *cptCar = compteur;
	return(tok);
	}

	/* operateur ou atome */

tok = (char *)malloc(i-compteur + 1);
strncpy(tok, stringExpr+compteur,i-compteur+1);
tok[i-compteur] = '\0' ;
*cptCar = i;
return(tok);
}

/*----------------------------------------------------------------------------
PMExpr   : Pattern Matching entre expr et pattern
           (and (not a) (not a)) avec le pattern (and x x) renvoie 1
------------------------------------------------------------------------------
retour   : 0 ou 1
------------------------------------------------------------------------------*/int PMExprInt(expr,pattern,bind)
chain_list *expr,*pattern;
ptype_list **bind;
{

if (ATOM(pattern))
   {
   ptype_list *find = getptype(*bind,VALUE_ATOM(pattern));
 
                /* le couple existe deja */

   if (find)
      {
      if (!equalExpr(expr, (chain_list *) find->DATA))
            return(0);
      }
   else
      *bind = addptype(*bind, VALUE_ATOM(pattern), expr);
 
   return(1);
   }
else
                /* pattern n'est pas un atome */
   {
   if (ATOM(expr))
      return(0);
   else
                /* expr n'est pas un atome */
      {
      if (OPER(expr) != OPER(pattern))
         return(0);
 
      if (lengthExpr(expr) != lengthExpr(pattern))
         return(0);
 
      while ((pattern = CDR(pattern)))
          {
          expr = CDR(expr);
          if (PMExprInt(CAR(expr),CAR(pattern),bind) == 0)
             return(0);
          }
      return(1);
      }
   }   
}
 
 
int PMExpr(expr,pattern)
chain_list *expr,*pattern;
{
int ret;
ptype_list *bind = NULL;

        /* on mettra dans "bind" le couple (char * pattern, expr) */

ret = PMExprInt(expr,pattern,&bind);
freeptype(bind);
return(ret);
}

