/* Differenzieren eines mathematischen Ausdruckes */
/* von Markus Öllinger */

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

typedef enum {OP_OPEN=-2,OP_CLOSE,OP_NONE=0,OP_ADD,OP_SUB,
	OP_MUL,OP_DIV,OP_NEG,OP_POT,OP_FUNC1} OP;

struct Knoten {
	struct Knoten *l,*r;
	OP Operator;
	short int Pri;
	short int Len;
	char *Term;
};

struct Knoten *Neuer_Operand(char *cp,char **x);
void verwende_Operator(OP);
struct Knoten *Differenziere(struct Knoten *);

extern char *Funktion[];

OP operator_stack[1024];	/* Der Operator-Stapel */
int sp_operator;	/* Sein Stapelzeiger */ 
struct Knoten *operand_stack[1024];
int sp_operand;

/* wandle Operatorenzeichen in Token um */

OP Operator(int op)
{
	switch(op) {
		case '+': return OP_ADD;
		case '-': return OP_SUB;
		case '*': return OP_MUL;
		case '/': return OP_DIV;
		case '_': return OP_NEG;
		case '^': return OP_POT;
	}
	return 0;
}

/* bestimme Priorität des Operators */

Pri(OP op)
{
	switch(op) {
		case OP_ADD:
		case OP_SUB: return 1;
		case OP_MUL:
		case OP_DIV: return 2;
		case OP_NEG: return 3;
		case OP_POT: return 4;
		case OP_NONE: return 0;
		default: return 5;
	}
}

/* konstruiere Baum aus String */

struct Knoten *Baum_aufbauen(char *term)
{
	char *cp=term;
	int i,l,pri,p;
	OP op,op2;
	char c;

	while((c=*cp)!=0) {
		if(c=='(') operator_stack[sp_operator++]=OP_OPEN;
		else if(isalnum(c)) {
			if(isalpha(c)) {
				for(i=0;Funktion[i];i++)
					if(!strncmp(Funktion[i],cp,l=strlen(Funktion[i]))) {
						pri=5;
						op=OP_FUNC1+i;
						cp+=l-1;
						goto operator;
					}
			}
			operand_stack[sp_operand++]=Neuer_Operand(cp,&cp);
			cp--;
		}
		else if(c==')')
			for(;;) {
				if(!sp_operator) goto error;
				op=operator_stack[--sp_operator];
				if(op!=OP_OPEN) verwende_Operator(op);
				else break;
			}
		else {
			op=Operator(c);
			pri=Pri(op);

				/* Subtraktion oder Negation? */

			if(op==OP_SUB && (cp==term || cp[-1]=='(')) {
				op=OP_NEG;
				pri=3;
			}
operator:	/* verwende alle Operatoren höherer Priorität */
			while(sp_operator) {
				op2=operator_stack[sp_operator-1];
				p=Pri(op2);

			/* Prioritätsvergleich. Achtung ^ ist rechtsassoziativ */

				if(op2==OP_OPEN || p<pri || p==pri && p==4)
					break;
				--sp_operator;
				verwende_Operator(op2);
			}
			operator_stack[sp_operator++]=op;
		}
		cp++;
	}
	while(sp_operator) {
		op2=operator_stack[--sp_operator];
		if(op2==OP_CLOSE) goto error;
		verwende_Operator(op2);
	}
	if(sp_operand!=1) goto error;
	return operand_stack[--sp_operand];
error:
	return NULL;
}

/* gibt Baum wieder frei (rekursiv, wie alles) */

void Baum_abbauen(struct Knoten *k)
{
	if(k) {
		if(k->l) Baum_abbauen(k->l);
		if(k->r) Baum_abbauen(k->r);
		free(k);
	}
}

	/* Hilfsroutinen */

struct Knoten *Neuer_Knoten(void)
{
	struct Knoten *k=malloc(sizeof(struct Knoten));
	if(k==NULL) {
		fprintf(stderr,"Speicher voll!\n");
		exit(10);
	}
	memset((void *)k,0,sizeof(*k));
	return k;
}

struct Knoten *Neuer_Operand(char *cp,char **x)
{
	struct Knoten *k;
	char *s;

	k=Neuer_Knoten();
	s=cp;
	while(*++s=='.' || isalnum(*s));
	k->Term=cp;
	k->Len=s-cp;
	*x=s;
	return k;
}

char *Op(OP op)
{
	static char c[]={" +-*/-^"};

	if(op>=OP_FUNC1) return Funktion[op-OP_FUNC1];
	return &c[op];
}

struct Knoten *Neuer_Operator(OP op)
{
struct Knoten *k;

	k=Neuer_Knoten();
	k->Operator=op;
	k->Pri=Pri(op);
	k->Term=Op(op);
	k->Len=op>=OP_FUNC1?strlen(k->Term):1;
	return k;
}

/* holt ein od. zwei Operanden vom Operandenstapel
 * und verknüpft sie mit dem angeg. Operator und
 * legt Ergebnis wieder zurück.
 */

void verwende_Operator(OP op)
{
	struct Knoten *k;
	int p=Pri(op);

	k=Neuer_Operator(op);
	k->r=operand_stack[--sp_operand];
	switch(p) {
		case 1:
		case 2:
		case 4:
			k->l=operand_stack[--sp_operand];
			k->Operator=op;
			k->Pri=p;
			break;
	}
	operand_stack[sp_operand++]=k;
}

/* erzeugt eine Kopie des Baumes */

struct Knoten *BaumKopie(struct Knoten *k)
{
	struct Knoten *n=NULL;

	if(k) {
		n=Neuer_Operator(OP_NONE);
		*n=*k;
		n->l=BaumKopie(k->l);
		n->r=BaumKopie(k->r);
	}
	return n;
}

/* Geht die in "Regel" gespeicherte Differenzierregel durch.
 * Diese ist in Präfixform gespeichert und hat folgende Syntax:
 * u entspricht dem linken Operanden (nicht differenziert)
 * a entspricht dem linken Operanden (aber differenziert)
 * v und b dasselbe rechts
 * + - * / ^ entsprechen den jeweilgen Operatoren.
 * _ entspricht dem (unären) Negationsoperator (Minus-Vorzeichen)
 * #XX entspricht einer Funktion, XX gibt die Funktionsnummer an.
 * #01 ist die Funktion mit dem im Feldelement Funktion[0]
 * gespeicherten Namen (hier ln), #02 entspr. Funktion[1] usw.
 * Eine Ziffer steht für die angegebene Zahl.
 *
 * in den globalen Variablen u, v, a und b werden die
 * gleichnamigen Teilbäume erwartet.
 */

char *Regel;	/*zu verwendende Regel*/
struct Knoten *u,*v,*a,*b;

/* Hier sind sie: die Differenzierregeln für
 * + - * / Negation und ^.
 */

char *dRegeln[]={
	NULL,"+ab","-ab","+*av*bu","/-*av*bu^v2",
	"_b","*^uv+*b#01u*/vua"};

/* Die Funktionsnamen und die Regeln für die Ableitung */

char *Funktion[]={"ln","sinh","cosh","sin","cos",
	"exp",NULL};
char *dFunk[]={"/bv","*#03vb","*#02vb","*#05vb","*_#04vb",
	"*#06vb"};

struct Knoten *Regeln(void)
{
	struct Knoten *k;
	int d;

	switch(d=*Regel++) {
		case 'a': k=BaumKopie(a);break;
		case 'b': k=BaumKopie(b);break;
		case 'u': k=BaumKopie(u);break;
		case 'v': k=BaumKopie(v);break;
		case '_': k=Neuer_Operator(OP_NEG);k->r=Regeln();break;
		case '#':	/* Funktion */
			sscanf(Regel,"%d",&d);
			Regel+=2;
			k=Neuer_Operator(d+OP_FUNC1-1);
			k->r=Regeln();
			break;
		default:
			if(isdigit(d)) {	/* Zahl */
				k=Neuer_Knoten();
				k->Term=Regel-1;
				k->Len=1;
			} else {		/* Operator */
				k=Neuer_Operator(Operator(d));
				k->l=Regeln();
				k->r=Regeln();
			}
	}
	return k;
}

/* erledigt das Differenzieren mittels Rekursion */

struct Knoten *Differenziere(struct Knoten *k)
{
	static char One='1',Zero='0';
	struct Knoten *d;

	if(k->Operator==OP_NONE) {		/* Blatt (Operand) */
		d=Neuer_Knoten();
		if(k->Len==1 && k->Term[0]=='x')
			d->Term=&One;
		else d->Term=&Zero;
		d->Len=1;
		return d;
	}
	if(k->Operator>=OP_FUNC1) {	/* Funktion */
		b=Differenziere(k->r);
		v=k->r;
		Regel=dFunk[k->Operator-OP_FUNC1];
		d=Regeln();
		Baum_abbauen(b);
		return d;
	}

		/* Operator */

	if(k->l) d=Differenziere(k->l);
	else d=NULL;
	b=Differenziere(k->r);
	a=d;
	u=BaumKopie(k->l);
	v=BaumKopie(k->r);
	Regel=dRegeln[k->Operator];
	d=Regeln();
	Baum_abbauen(u);
	Baum_abbauen(v);
	Baum_abbauen(a);
	Baum_abbauen(b);
	return d;
}

	/* Baum zurück in String umwandeln */

/* hat der Vater v einen Sohn s mit einem Operator
 * niedrigerer Priorität?
 */

pri_klammer(struct Knoten *v,struct Knoten *s,char **sp)
{
	if(v->Pri>s->Pri && s->Pri!=0 || v->Pri==s->Pri && v->Pri==4) {
		(*sp)[0]='(';
		(*sp)++;
		return 1;
	}
	return 0;
}

/* mach ev. Klammer wieder zu */

void klammer_zu(char **sp,int kl)
{
	if(kl) {
		(*sp)[0]=')';
		(*sp)++;
	}
}

void Baum_zu_String(struct Knoten *k,char *s)
{
	extern char *Baum_String(struct Knoten *,char *);
	*Baum_String(k,s)=0;
}

char *Baum_String(struct Knoten *k,char *s)
{
	int kl;

	if(k->Operator==OP_NONE) {
		strncpy(s,k->Term,k->Len);
		s+=k->Len;
		return s;
	}
	if(k->Operator>=OP_FUNC1) {
		strncpy(s,k->Term,k->Len);
		s+=k->Len;
		kl=pri_klammer(k,k->r,&s);
		if(!kl) *s++=' ';
		s=Baum_String(k->r,s);
		klammer_zu(&s,kl);
		return s;
	}
	if(k->Operator==OP_NEG) {
		*s++='-';
		kl=pri_klammer(k,k->r,&s);
		s=Baum_String(k->r,s);
		klammer_zu(&s,kl);
		return s;
	}
	kl=pri_klammer(k,k->l,&s);
	if(!kl && k->Operator==OP_POT && k->l->Operator==OP_POT) {
		*s++='(';
		kl=1;
	}
	s=Baum_String(k->l,s);
	klammer_zu(&s,kl);
	*s++=*Op(k->Operator);
	kl=pri_klammer(k,k->r,&s);
	if(!kl && (k->Operator==OP_SUB || k->Operator==OP_DIV) && k->r->Pri==k->Pri) {
		*s++='(';
		kl=1;
	}
	s=Baum_String(k->r,s);
	klammer_zu(&s,kl);
	return s;
}

	/*** Einsprung zum Differenzieren
	 *** (Term muß korrekt sein)
	 ***/

void Diff(char *Angabe,char *Ergebnis)
{
	struct Knoten *Root,*d;

	Root=Baum_aufbauen(Angabe);
	Baum_zu_String(Root,Ergebnis);
	puts(Ergebnis);
	d=Differenziere(Root);
	Baum_zu_String(d,Ergebnis);
	Baum_abbauen(d);
	Baum_abbauen(Root);
}

/* nur ein kurzer Check */

Term_korrekt(char *term)
{
	char c,*lastop=NULL,*p=term,*cp=term-1;
	int kl=0;

	while((c=*++cp)!=0) if(!isspace(c)) {
		if(strchr("()+-*/^",c)) {
			if(c=='(') kl++;
			else if(c==')') {
				if(--kl<0 || lastop+1==cp || cp[-1]=='(') return 0;
			}
			else {
				if(lastop+1==cp || c!='-' && cp[-1]=='(') return 0;
				lastop=cp;
			}
		}
		else if(!isalnum(c) && c!='.') return 0;
		*p++=c;
	}
	*p=0;
	return kl==0;
}

char Angabe[1024],Ergebnis[1024];

void main(int argc,char **argv)
{
	if(argc==2 && Term_korrekt(strcpy(Angabe,argv[1]))) {
		Diff(Angabe,Ergebnis);
		puts(Ergebnis);
	}
}