Arbres syntaxiques

sTree.c

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include"sTree.h"

/***********************************************************/

/*
  Cree un noeud de l'arbre syntaxique.
*/

sTree* createSTree(char type, int data, sTree* left, sTree* right)
{
  sTree* s = (sTree*)malloc(sizeof(sTree));
  if (s == NULL)
    {
      printf("no memory left...\n");
      exit(0);
    }
  s->type = type;
  s->data = data;
  s->left = left;
  s->right = right;
  return s;
}

/***********************************************************/

sTree* createConstantSTree(int constant)
{
  return createSTree(CONSTANT, constant, NULL, NULL);
}

/***********************************************************/

sTree* createOperatorSTree(int operator, sTree* left, sTree* right)
{
  return createSTree(OPERATOR, operator, left, right);
}

/***********************************************************/

sTree* createVariableSTree()
{
  return createSTree(VARIABLE, 0, NULL, NULL);
}

/***********************************************************/

sTree* createLnSTree(sTree* arg)
{
  return createSTree(LN, LN, arg, NULL);
}

/***********************************************************/

void printSTree(sTree* s)
{
  if (s != NULL)
    {
      switch(s->type)
	{
	case CONSTANT : 
	  printf("%d", s->data);
	  break;
	case VARIABLE : 
	  printf("%c", VARIABLE);
	  break;
	case LN : 
	  printf("(ln ");	
	  printSTree(s->left);
	  printf(")");
	  break;
	default : 
	  printf("(");	
	  printSTree(s->left);
	  printf("%c", s->data);
	  printSTree(s->right);
	  printf(")");
	}      
    }
}

/***********************************************************/

void destroySTree(sTree* s)
{
  if (s != NULL)
    {
      destroySTree(s->left);
      destroySTree(s->right);
      free(s);
    }
}

/***********************************************************/

float evaluateSTree(sTree* s, float x)
{
  if (s == NULL)
    {
      printf("STree can't be empty !");
      exit(0);
    }
      switch(s->type)
	{
	case CONSTANT : 
	  return s->data;
	case VARIABLE : 
	  return x;
	default : 
	  switch(s->data)
	    {
	    case PLUS : 
	      return evaluateSTree(s->left, x) + evaluateSTree(s->right, x);
	    case MINUS : 
	      return evaluateSTree(s->left, x) - evaluateSTree(s->right, x);
	    case TIMES : 
	      return evaluateSTree(s->left, x) * evaluateSTree(s->right, x);
	    case DIV : 
	      return evaluateSTree(s->left, x) / evaluateSTree(s->right, x);
	    case LN : 
	      return log(evaluateSTree(s->left, x));
	    default:
	      return pow(evaluateSTree(s->left, x), 
			      evaluateSTree(s->right, x));
	    }
	}      
}

/***********************************************************/

sTree* copySTree(sTree* s)
{
  if (s == NULL)
    return NULL;
  return createSTree(s->type, s->data, 
		     copySTree(s->left), copySTree(s->right)); 
}

/***********************************************************/

sTree* derivateProduct(sTree* s, int sign)
{
  sTree* left = createOperatorSTree(TIMES,
				    derivateSTree(s->left),
				    copySTree(s->right));
  sTree* right = createOperatorSTree(TIMES,
				     copySTree(s->left),
				     derivateSTree(s->right));  
  return createOperatorSTree(sign, left, right);     
}

/***********************************************************/

sTree* derivateRationnal(sTree* s)
{
  sTree* numerator = derivateProduct(s, MINUS);
  sTree* denominator = createOperatorSTree(EXP, copySTree(s->right), 
					   createConstantSTree(2));     
  return createOperatorSTree(DIV, numerator, denominator);
}

/***********************************************************/

sTree* derivateExp(sTree* s)
{
  sTree* tmp, *left;
  tmp = createOperatorSTree(TIMES,
			    copySTree(s->right), 
			    createLnSTree(copySTree(s->left)));
  left = derivateSTree(tmp);
  destroySTree(tmp);
  return createOperatorSTree(TIMES,
		      left, 
		      copySTree(s));
}

/***********************************************************/

sTree* derivateLn(sTree* s)
{
  sTree* numerator = derivateSTree(s->left);
  sTree* denominator = copySTree(s->left);
  return createOperatorSTree(DIV, numerator, denominator);
}

/***********************************************************/

sTree* derivateSTree(sTree* s)
{
  if (s == NULL)
    return NULL;
  switch(s->type)
    {
    case CONSTANT : 
      return createConstantSTree(0); 
    case VARIABLE : 
      return createConstantSTree(1); 
    default :
      switch(s->data)
	{
	case PLUS : 
	  return createOperatorSTree(PLUS, 
				     derivateSTree(s->left), 
				     derivateSTree(s->right));
	case MINUS : 
	  return createOperatorSTree(MINUS, 
				     derivateSTree(s->left), 
				     derivateSTree(s->right));
	case TIMES : 
	  return derivateProduct(s, PLUS);     
	case DIV : 
	  return derivateRationnal(s);     
	case LN : 
	  return derivateLn(s);     
	default:
	  return derivateExp(s);
	}
    }
}

/***********************************************************/

sTree* nDerivateSTree(sTree* s, int n)
{
  if (n == 0)
    return copySTree(s);
  if (n == 1)
    return derivateSTree(s);
  sTree* tmp = nDerivateSTree(s, n - 1);
  s = derivateSTree(tmp);
  destroySTree(tmp);
  return s;
}

/***********************************************************/

float integrateSTree(sTree* s, float a, float b, int nbTrapezes)
{
  if (a > b)
    return - integrateSTree(s, b, a, nbTrapezes);
  float sum, step = (b - a) / nbTrapezes, x = a + step;
  sum = (evaluateSTree(s, a) + evaluateSTree(s, b))/2;
  while(x < b)
    {
      sum += evaluateSTree(s, x);
      x+=step;
    }
  return sum*step;
}

stackTree.c

#include"stackTree.h"

/***********************************************************/

stackTree* createST(sTree* s, stackTree* next)
{
  stackTree* st = (stackTree*)malloc(sizeof(stackTree));
  if (st == NULL)
    {
      printf("no memory left...\n");
      exit(0);
    }
  st->s = s;
  st->next = next;
  return st;
  }

/***********************************************************/

void printST(stackTree* st)
{
  if (st != NULL)
    {
      printST(st->next);
      printf("->");
      printSTree(st->s);
    }
}

/***********************************************************/

/*ne detruit pas les arbres*/

void destroyST(stackTree* st)
{
  if (st != NULL)
    {
      destroyST(st->next);
      free(st);
    }
}

/***********************************************************/

int isEmptyST(stackTree* st)
{
  return st == NULL;
}

/***********************************************************/

stackTree* pushST(stackTree* st, sTree* s) 
{
  return createST(s, st);
}

/***********************************************************/

sTree* topST(stackTree* st)
{
  if (isEmptyST(st))
    {
      printf("Empty stack has no top.\n");
      exit(0);      
    }
  return st->s;
}

/***********************************************************/

stackTree* popST(stackTree* st)
{
  if (isEmptyST(st))
    {
      printf("Can't pop empty stack.\n");
      exit(0);      
    }
  stackTree* next = st->next;
  st->next = NULL;
  destroyST(st);
  return next;
}

/***********************************************************/

stackTree* addConstantST(stackTree* st, int constant)
{
  return pushST(st, createConstantSTree(constant));
}

/***********************************************************/

stackTree* addVariableST(stackTree* st)
{
  return pushST(st, createVariableSTree());
}

/***********************************************************/

stackTree* addOperatorST(stackTree* st, int operator)
{
  sTree* left, *right;
  right = topST(st);
  st = popST(st);
  left = topST(st);
  st = popST(st);
  return pushST(st, createOperatorSTree(operator, left, right));
}

/***********************************************************/

stackTree* addLnST(stackTree* st, int operator)
{
  sTree* arg;
  arg = topST(st);
  st = popST(st);
  return pushST(st, createLnSTree(arg));
}

parser.c

#include"parser.h"

int isAnOperator(char c)
{
  return c==PLUS || c==MINUS || c==TIMES || c==DIV || c==EXP;
}

/***********************************************************/

int isANumber(char c)
{
  return c>= '0' && c <= '9';
}

/***********************************************************/

int isAVariable(char c)
{
  return c == VARIABLE;
}

/***********************************************************/

int isLn(char c)
{
  return c == LN;
}

/***********************************************************/

int intOfChar(char a)
{
  return a - '0';
}

/***********************************************************/

int intOfStrAux(char* c, int acc)
{
  if (!isANumber(*c))
    return acc;
  return intOfStrAux(c + 1, intOfChar(*c) + 10 * acc);
}


/***********************************************************/

int intOfStr(char* c)
{
  return intOfStrAux(c, 0);
}

/***********************************************************/

stackTree* addNodeST(stackTree* st, char* s)
{
  if (s==NULL)
    return st;
  if (isAVariable(*s))
    return addVariableST(st);
  if (isAnOperator(*s))
    return addOperatorST(st, *s);
  if (isLn(*s))
    return addLnST(st, *s);
  if (isANumber(*s))
    return addConstantST(st, intOfStr(s));
  printf("Parse error in expression %s.\n", s);
  return NULL;
}

/***********************************************************/

int isADelimitor(char c)
{
  return !(isLn(c) || isAVariable(c) || isANumber(c) || isAnOperator(c));
}

/***********************************************************/

char* findDelimitor(char* str)
{
  while(!isADelimitor(*str))
    {
      str++;
    }
  return str;
}

/***********************************************************/

char* skipDelimitors(char* str)
{
  while(isADelimitor(*str))
    {
      str++;
    }
  return str;
}

/***********************************************************/

int splitStr(char* str, char** adresses)
{
  int res = 1;
  if (*str == 0)
    return 0;
  *adresses = str;
  adresses++;
  *adresses = str + 1;
  while(**adresses != 0)
    {
      *adresses = skipDelimitors(findDelimitor(*adresses));
      *(adresses + 1) = *adresses + 1;
      adresses++;
      res ++;
    }
  return res;
}

/***********************************************************/

sTree* parseExpression(char* exp)
{
  char* adresses[MAX_SIZE];
  int i, nbTokens = splitStr(exp, adresses);
  stackTree* st = NULL;
  sTree* r;
  for(i = 0 ; i < nbTokens ; i++)
    st = addNodeST(st, *(adresses + i));
  r = topST(st);
  st = popST(st);
  if (!isEmptyST(st))
    {
      printf("error while parsing %s\n", exp);
      destroyST(st);
    }
  return r;
}