/*

  __                                       __
 /\ \                 __                  /\ \__  __
 \_\ \     __   _ __ /\_\  __  __     __  \ \ ,_\/\_\    ___     ___
 /'_` \  /'__`\/\`'__\/\ \/\ \/\ \  /'__`\ \ \ \/\/\ \  / __`\ /' _ `\
/\ \L\ \/\  __/\ \ \/ \ \ \ \ \_/ |/\ \L\.\_\ \ \_\ \ \/\ \L\ \/\ \/\ \
\ \___,_\ \____\\ \_\  \ \_\ \___/ \ \__/.\_\\ \__\\ \_\ \____/\ \_\ \_\
 \/__,_ /\/____/ \/_/   \/_/\/__/   \/__/\/_/ \/__/ \/_/\/___/  \/_/\/_/


AUTEUR	: Aymeric & Samira
GROUPE	: 5 (RT)
DATE	: 15/05/2003
FICHIER	: derivation.cpp

*/


#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include "derivation.h"

// Mettre a 1 pour passer en mode debug
#define debug 0


/*
 ---------------------------------------------------------------
|		Declaration des fonctions			|
 ---------------------------------------------------------------
*/

noeud* creer_noeud(char,double,char,noeud*,noeud*);
void copie_noeud(noeud*,noeud*&);
void mystrtoupper(char[]);
Arbre deriver(Arbre);
noeud * deriver_noeud(noeud*);
noeud * deriver_racine(noeud*);
Arbre simplifier(Arbre);
noeud * simplifier_noeud(noeud*);

void error(int);
void lecture();
void expression(noeud *&);
void terme(noeud *&);
void facteur(noeud *&);
void variable(noeud *&);
void decimal(noeud *&);
void valeur(noeud *&,bool);
void chiffre(noeud *&,bool);


/*
 ---------------------------------------------------------------
|		Declaration des variables gloables		|
 ---------------------------------------------------------------
*/

// 'calu' represente la lettre qu'on etudiera pour la syntaxe
char calu;
// 'calcul' est la fonction a deriver
char calcul[1024];
// 'pos' represente la position de la lettre etudiee dans 'calcul'
int pos=0;
// 'exposant' est utilisee pour les chiffres decimaux
int exposant=0;


/*
 ---------------------------------------------------------------
|			Fonction MAIN				|
 ---------------------------------------------------------------
*/

int main(void)
{
	int longueur;
	cout << "\033[H\033[J";
	cout << "\t------------------------------------" << endl;
	cout << "\t- Derivation d'une fonction simple -" << endl;
	cout << "\t------------------------------------" << endl << endl;
	do
	{
		cout << "\nRentrez la chaine a deriver (1023 caracteres max) : " << endl;
		cin >> calcul;
		longueur=strlen(calcul);
	} while (longueur > 1023);
	
	// on place le caractere special en fin de chaine pour le test de fin
	calcul[longueur]='$';
	calcul[++longueur]='\0';
		
	// on met tout en majuscule
	mystrtoupper(calcul);
	
	// on lit le premier caractere
	lecture();

	noeud *r=NULL;
	
	// on appelle expression() pour verifier la syntaxe de la chaine rentree
	expression(r);

	// si on ne tombe pas sur '$' la syntaxe est incorrecte
	if (calu != '$') error(10);
	else cout << "Syntaxe ok !" << endl << endl;
	
	// on cree un arbre representant le calcul rentre
	Arbre arbuste(r);

	// on affiche le calcul
	arbuste.affiche();
	cout << "' = ";
	
	// on cree un nouvel arbre contenant le resultat de la derivee
	Arbre resultat=deriver(arbuste);

	// puis on affiche le resultat non simplifie
	resultat.affiche();

	cout << endl;
	arbuste.affiche();
	cout << "' = ";
	// enfin on affiche le resultat simplifie
	resultat=simplifier(resultat);
	resultat.affiche();

	cout << endl << "\n- Fin du programme -" << endl << endl;
}



/*
 ---------------------------------------------------------------
|		Fonctions de la classe Arbre			|
 ---------------------------------------------------------------
*/

// constructeur
Arbre :: Arbre(noeud *n)
{
	racine=n;
}

// destructeur
Arbre :: ~Arbre()
{
	liberearbre(racine);
}

void Arbre :: liberearbre(noeud * aux)
{
	if (aux == NULL) return;
	liberearbre(aux->fg);
	liberearbre(aux->fd);
	delete aux;
}

void Arbre :: affiche()
{
	affiche_noeud(racine);
}

void Arbre :: affiche_noeud(noeud *rac)
{
	if ( (rac->fg == NULL) && (rac->fd == NULL) )
	{
		if ( rac->type == 'R' ) cout << " " << rac->var;
		else cout << " " << rac->val;
	}
	else
	{
		if (rac->type == 'O') cout << " (";
		if (rac->fg != NULL) affiche_noeud(rac->fg);

		cout << " " << rac->ope;

		if (rac->fd != NULL) affiche_noeud(rac->fd);
		if (rac->type == 'O') cout << " )";
	}
}


/*
 ---------------------------------------------------------------
|		Fonctions utilisees par le programme		|
 ---------------------------------------------------------------
*/

// fonction qui permet de creer un nouveau noeud selon les parametres
noeud* creer_noeud(char _type, double _val, char _ope_var, noeud *_fg, noeud *_fd)
{
	noeud *n=new noeud;
	n->type=_type;
	n->fg=_fg;
	n->fd=_fd;

	if ( (_type == 'O') || (_type == 'R') ) n->ope=_ope_var;
	else if (_type == 'L') n->val=_val;

	return(n);
}

// fonction permettant de copier le contenu d'un noeud source vers un noeud destination
void copie_noeud(noeud *source, noeud *&dest)
{
	if (source == NULL) return;
	if (dest == NULL) dest=new noeud;
	dest->type=source->type;
	if (source->type == 'R') dest->var=source->var;
	else if (source->type == 'L') dest->val=source->val;
	else if (source->type == 'O') dest->ope=source->ope;
	copie_noeud(source->fg,dest->fg);
	copie_noeud(source->fd,dest->fd);
}

// cette fonction met en majuscule une chaine de caracteres
void mystrtoupper(char s[])
{
	int i=0;
	while (s[i] != '\0')
	{
		if ((s[i] >= 'a') && (s[i] <= 'z'))
			s[i] -= 32;
		i++;
	}
}


/*
 ---------------------------------------------------------------
|		Fonctions pour la derivation			|
 ---------------------------------------------------------------
*/

Arbre deriver(Arbre a)
{
	noeud *rac=new noeud;
	copie_noeud(a.racine,rac);
	Arbre result(deriver_racine(rac));
	return(result);
}

noeud* deriver_racine(noeud *rac)
{
	if ( (rac->fg == NULL) && (rac->fd == NULL) ) rac=deriver_noeud(rac);
	else
	{
		if ( rac->type == 'O' )
		{
			if ( (rac->ope == '+') || (rac->ope == '-') )
			{
				// (u+v)' = u' + v'
				// (u-v)' = u' - v'
				rac->fg = deriver_racine(rac->fg);
				rac->fd = deriver_racine(rac->fd);
			}
			else if ( rac->ope == '*' )
			{
				// (u*v) ' = u'v - v'u
				noeud *uprime,*u=new noeud;
				noeud *vprime,*v=new noeud;
				
				// on enregistre u et v
				copie_noeud(rac->fg,u);
				copie_noeud(rac->fd,v);
				
				// on derive 'u en u' et v en v'
				uprime = deriver_racine(rac->fg);
				vprime = deriver_racine(rac->fd);
				
				noeud *op2;
				noeud *op3;
				op2=creer_noeud('O',0,'*',uprime,v);
				op3=creer_noeud('O',0,'*',u,vprime);
				rac=creer_noeud('O',0,'+',op2,op3);
			}
			else if ( rac->ope == '/' )
			{
				// (u/v)' = (u'v - v'u) / v*v
				noeud *uprime;
				noeud *vprime;
				
				// on derive u en u' et v en v'
				uprime = deriver_racine(rac->fg);
				vprime = deriver_racine(rac->fd);
				
				noeud *u=new noeud;
				noeud *v=new noeud;
				
				// on enregistre u et v
				copie_noeud(rac->fg,u);
				copie_noeud(rac->fd,v);
				
				noeud *op2;
				noeud *op3,*op1;
				op2=creer_noeud('O',0,'*',uprime,v);
				op3=creer_noeud('O',0,'*',u,vprime);
				op1=creer_noeud('O',0,'-',op2,op3);

				noeud *op4;
				op4=creer_noeud('O',0,'*',v,v);
				rac=creer_noeud('O',0,'/',op1,op4);
			}
		}
	}
	return(rac);
}

noeud * deriver_noeud(noeud *n)
{
	noeud *aux=new noeud;
	if ( n == NULL ) return(NULL);
	if ( (n->fg == NULL) && (n->fd == NULL) )
	{
		// si le type est 'L' c'est-a-dire une VALEUR, on change la valeur en 0
		// car (constante)' = 0
		if (n->type == 'L')
		{
			aux->type=n->type;
			aux->val=0;
		}
		// si le type est 'R' c'est-a-dire VARIABLE, on change le type en 'L' et on met la valeur 1
		else if (n->type == 'R')
		{
			aux->type='L';
			if ( (n->var == 'Y') || (n->var == 'Z') ) aux->val=0;
			else aux->val=1;
		}
		aux->fg=n->fg;
		aux->fd=n->fd;
	}
	return (aux);

}


/*
 ---------------------------------------------------------------
|		Fonctions pour la simplification		|
 ---------------------------------------------------------------
*/

Arbre simplifier(Arbre a)
{
	a.racine=simplifier_noeud(a.racine);
	return(a);
}

noeud* simplifier_noeud(noeud * n)
{
	if ( (n->fg->type == 'O') ) n->fg=simplifier_noeud(n->fg);
	if ( (n->fd->type == 'O') ) n->fd=simplifier_noeud(n->fd);

	// valeur1+valeur2=valeur3
	// valeur1-valeur2=valeur3
	// valeur1*valeur2=valeur3
	// valeur1/valeur2=valeur3
	if ( (n->fg->type == 'L') && (n->fd->type == 'L') )
	{
		n->type='L';
		if (n->ope == '+') n->val=n->fg->val + n->fd->val;
		if (n->ope == '-') n->val=n->fg->val - n->fd->val;
		if (n->ope == '*') n->val=n->fg->val * n->fd->val;
		if (n->ope == '/') n->val=n->fg->val / n->fd->val;
		delete(n->fg);
		delete(n->fd);
		n->fg=NULL;
		n->fd=NULL;
	}
	// 0 + X = X ou X + O = X
	else if (n->ope == '+')
	{
		if ( (n->fg->type == 'L') && (n->fg->val == 0) ) n=n->fd;
		else if ( (n->fd->type == 'L') && (n->fd->val == 0) ) n=n->fg;
	}
	// X - 0 = X
	else if (n->ope == '-')
	{
		if ( (n->fd->type == 'L') && (n->fd->val == 0) ) n=n->fg;
	}
	else if (n->ope=='*')
	{
		// 0 * X = 0 ou X * 0 = 0
		if ( ((n->fg->type == 'L') && (n->fg->val == 0)) || ((n->fd->type == 'L') && (n->fd->val == 0)) )
		{
			delete(n->fg);
			delete(n->fd);
			n->fg=NULL;
			n->fd=NULL;
			n->type='L';
			n->val=0;
		}
		// 1 * X = X
		else if ( (n->fg->type == 'L') && (n->fg->val == 1) ) n=n->fd;
		// X * 1 = X
		else if ( (n->fd->type == 'L') && (n->fd->val == 1) ) n=n->fg;
	}
	else if (n->ope == '/')
	{
		// X / 1 = X
		if ( (n->fd->type == 'L') && (n->fd->val == 1) ) n=n->fg;
	}
	return(n);
}


/*
 ---------------------------------------------------------------
|			Verification syntaxique			|
 ---------------------------------------------------------------
*/

// fonction qui affiche les erreurs de syntaxe
void error(int param)
{
	switch(param)
	{
		case 0:  cout << "\nErreur " << param << ": Fin de chaine non attendue !\n";
			 break;
		case 1:  cout << "\nErreur " << param << ": Manque parenthese fermante !\n";
			 break;
		case 2:  cout << "\nErreur " << param << ": " << calu << " <= Variable inconnue !\n";
			 break;
		case 3:  cout << "\nErreur " << param << ": " << calu << " <= Chiffre inconnu !\n";
			 break;
		case 10: cout << "\nErreur " << param << ": Mauvaise syntaxe (mauvais argument)\n";
			 break;
		default: break;
	}
	exit(param);
}

// fonction qui decale le pointeur dans 'calcul'
void lecture()
{
	if (calcul[pos] != '\0')
	{
		calu=calcul[pos];
		pos++;
		if (debug) cout << "\nOn lit " << calu;
	}
	else error(0);
}

void expression(noeud *& ret)
{
	noeud *t=NULL;
	noeud *e=NULL;
	if (debug) cout << "\nexpression";
	terme(t);
	if ( (calu == '+') || (calu == '-') )
	{
		char ope=calu;
		lecture();
		expression(e);
		ret=creer_noeud('O',0,ope,t,e);
	}
	else copie_noeud(t,ret);
}

void terme(noeud *& ret)
{
	noeud *t=NULL;
	if (debug) cout << "\nterme";
	facteur(ret);
	if ( (calu == '*') || (calu == '/') )
	{
		char ope=calu;
		lecture();
		terme(t);
		ret=creer_noeud('O',0,ope,ret,t);
	}
}

void facteur(noeud *& ret)
{
	if (debug) cout << "\nfacteur";
	if (calu == '(')
	{
		lecture();
		expression(ret);
		if (calu == ')') lecture();
		else error(1);
	}
	else if ( (calu == 'X') || (calu == 'Y') || (calu == 'Z') ) variable(ret);
	else decimal(ret);
}

void variable(noeud *& ret)
{
	if (debug) cout << "\nvariable";
	if ( (calu == 'X') || (calu == 'Y') || (calu == 'Z') )
	{
		ret=creer_noeud('R',0,calu,NULL,NULL);
		lecture();
	}
	else error(2);
}

void decimal(noeud *& ret)
{
	if (debug) cout << "\ndecimal";
	valeur(ret,false);
	if ( (calu == '.') || (calu == ',') )
	{
		lecture();
		// si on tape un decimal, on passe TRUE comme parametre pour 'virgule'
		valeur(ret,true);
	}
}

void valeur(noeud *& ret, bool virgule)
{
	if (debug) cout << "\nvaleur";
	chiffre(ret,virgule);
	if ( (calu >= '0') && (calu <= '9') ) valeur(ret,virgule);
	exposant=0;
}

void chiffre(noeud *& ret, bool virgule)
{
	if (debug) cout << "\nchiffre";

	if ( (calu >= '0') && (calu <= '9') )
	{
		// si on a aucun chiffre, on cree le noeud
		if (ret == NULL) ret=creer_noeud('L',calu-48,0,NULL,NULL);
		else
		{
			// si le noeud existe deja, et que virgule est a FALSE (cad que c'est une valeur non decimal)
			// on utilise la fonction de Horner
			if (virgule == false) ret->val=ret->val*10+(calu-48);
			// sinon c'est un chiffre decimal donc on fait un calcul du genre :
			// X=X+(calu/10ªn)
			else
			{
				int dec=1;
				int negatif=1;
				exposant++;
				for (int i=0; i < exposant; i++) dec=dec*10;
				if (ret->val < 0)
				{
					negatif=-1;
					ret->val=ret->val*-1;
				}
				ret->val=(double)ret->val+(((double)calu-48)/dec);
				ret->val=ret->val*negatif;
			}
		}
		lecture();
	}
	// si on a un chiffre negatif
	else if ( calu == '-' )
	{
		lecture();
		if ( (calu >= '0') && (calu <= '9') )
		{
			ret=creer_noeud('L',(calu-48)*-1,0,NULL,NULL);
			lecture();
		}
		else error(3);
	}
	else error(3);
}