#include <ctype.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <intuition/intuition.h>
#include <proto/intuition.h>
#include <proto/exec.h>
#include <proto/graphics.h>

struct bits {unsigned K:1,Neg:1,Konst:1;};
typedef union {unsigned mask;struct bits is;} FLAGS;
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_USERF=100} OP;
typedef enum {PRI_NONE,PRI_ADDSUB,PRI_MULDIV,PRI_NEG,PRI_POT,PRI_FUNC} PRI;
struct Knoten {
 FLAGS flags; OP op; PRI pri;
 short primes;
 struct Knoten *links,*rechts;
 double konst;
 short len; char *term;
} *Root;
BOOL verwende(OP);
struct Knoten *Verschmelze(struct Knoten *,struct Knoten *),
 *Vereinfache(struct Knoten *,struct Knoten *,PRI,struct Knoten *,struct Knoten *,int),
 *Verkette(struct Knoten *,OP,struct Knoten *);
char *Baum_String(struct Knoten *,char *),
 *Baum_zu_String(struct Knoten *,char *);
struct Knoten *Differenziere(struct Knoten *,struct list *),*Regeln(void);

char Puffer1[1024],Puffer2[1024],Puffer3[1024],Puffer4[1024];
char *cp,*term,*Beginn;
char *Funktionen[]={"ln","sinh","cosh","sin","cos",
"tanh","coth","tan","cot","log","arcsin","arccos",
"arctan","arccot","sqrt","arsinh","arcosh",
"artanh","arcoth","exp",NULL};
char *FunkMsg[]={"z'/z","z'*cosh z","z'*sinh z","z'*cos z","z'*(-sin z)",
"z'/(cosh z)^2","-z'/(sinh z)^2","z'/(cos z)^2","-z'/(sin z)^2",
"z'/z*log e","z'/sqrt(1-z^2)","-z'/sqrt(1-z^2)",
"z'/(1+z^2)","-z'/(1+z^2)","z'/(2*sqrt(z))","z'/sqrt(1+z^2)",
"z'/sqrt(z^2-1)","z'/(1-z^2)","z'/(1-z^2)","z'*exp(z)"};

OP op_stack[1024];
int op_sp,kn_sp;
struct Knoten *kn_stack[1024];
PRI oppri[]={PRI_NONE,PRI_ADDSUB,PRI_ADDSUB,
PRI_MULDIV,PRI_MULDIV,PRI_NEG,PRI_POT};
PRI Pri(OP op) {return op<OP_FUNC1?oppri[op]:PRI_FUNC;}
char chop[]={"+-*/_^"};
#define opnr(c) ((OP)(strchr(chop,c)-chop)+OP_ADD)
#define Op(op) ((op)<OP_FUNC1?&chop[(op)-1]:Funktionen[(op)-OP_FUNC1])
#define kommOp(op) ((op)==OP_MUL || (op)==OP_DIV ? OP_MUL : OP_ADD)
#define nkommOp(op) ((op)==OP_MUL || (op)==OP_DIV ? OP_DIV : OP_SUB)
#define StdKonst(pri) ((pri)==PRI_ADDSUB?0.:1.)
#define inv_konst(d,pri) ((d)?(pri)==PRI_ADDSUB?-(d):1./(d):(errno=EDOM,0.))
#define X(k) ((k)->op==OP_NONE && (k)->len==1 && (k)->term[0]=='x')
#define C(k) ((k)->op==OP_NONE && (k)->flags.is.Konst)

void inv_K(struct Knoten *k, PRI pri)
{
  struct Knoten *n=k->links;
  k->links=k->rechts; k->rechts=n;
  k->konst=inv_konst(k->konst,pri);
}

void Rechne(struct Knoten *l,OP op,struct Knoten *r)
{
  switch(op) {
    case OP_ADD: l->konst+=r->konst; break;
    case OP_SUB: l->konst-=r->konst; break;
    case OP_MUL: l->konst*=r->konst; break;
    case OP_DIV: if(r->konst) l->konst/=r->konst;
      else errno=EDOM; break;
  }
}

void Negiere(struct Knoten *k)
{
  struct Knoten *n;
  if(k->pri==PRI_ADDSUB) {
    k->konst=-k->konst; n=k->links;
    k->links=k->rechts; k->rechts=n;
  }
  else if((k->pri==PRI_MULDIV || k->op==OP_NONE) && k->flags.is.Konst)
    k->konst=-k->konst;
  else k->flags.is.Neg=!k->flags.is.Neg;
}

BOOL Term_korrekt(char *term)
{
char c,*lastop=NULL,*p=term;
int kl=0;
  cp=term-1;
  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 FALSE;
      } else {
        if(lastop+1==cp || c!='-' && cp[-1]=='(') return FALSE;
        lastop=cp;
      }
    }
    else if(!isalnum(c) && !strchr(".'",c)) return FALSE;
    *p++=c;
  }
  *p=0; return (BOOL)(kl==0);
}

struct Knoten *Neuer_Operator(OP op)
{
struct Knoten *k;
  if(!(k=malloc(sizeof(struct Knoten)))) {
    fprintf(stderr,"Speicher voll!\n");
    exit(10);
  }
  k->links=k->rechts=NULL;
  k->flags.mask=0; k->primes=0;
  k->op=op; k->pri=Pri(op);
  if(op<OP_USERF) {
    k->term=Op(op);
    k->len=op>=OP_FUNC1?strlen(k->term):1;
  }
  else {int i;
    k->op=OP_USERF;
    k->term=term+op-OP_USERF;
    if(!strncmp(k->term,"log",3)) k->op=OP_FUNC1+9;
    for(i=0;isalnum(k->term[i]);i++);
    k->len=i;
    while(k->term[i++]=='\'') k->primes++;
  }
  k->konst=0.; return k;
}

struct Knoten *NeuerK(OP op)
{
  struct Knoten *k=Neuer_Operator(nkommOp(op));
  k->flags.is.K=k->flags.is.Konst=1;
  k->konst=StdKonst(k->pri);
  return k;
}

struct Knoten *Neue_Konst(double d)
{
  struct Knoten *k=Neuer_Operator(OP_NONE);
  k->flags.is.Konst=1;
  k->konst=d; return k;
}

struct Knoten *Neues_Blatt(char *cp,char **x)
{
struct Knoten *k=Neuer_Operator(OP_NONE);
char *s;
  if(isdigit(*cp)) {
    sscanf(cp,"%lf",&k->konst);
    if(!(s=strpbrk(cp,"()+-*^/"))) s=strchr(cp,0);
    k->flags.is.Konst=1;
  }
  else {
    k->konst=0.; s=cp;
    while(isalnum(*++s));
  }
  k->term=cp; k->len=s-cp;
  *x=s; return k;
}

struct Knoten *Baum_aufbauen(char *cp)
{
int i,l; char c;
PRI p,p2; OP op,op2;
  term=cp;
  while((c=*cp)!=0) {
    if(c=='(') op_stack[op_sp++]=OP_OPEN;
    else if(isalnum(c)) {
      if(isalpha(c)) {
        for(i=0;Funktionen[i];i++)
          if(!strncmp(Funktionen[i],cp,l=strlen(Funktionen[i]))) {
            op=OP_FUNC1+i;
            if(op==OP_FUNC1+9) {
              op=(cp-term)+OP_USERF;
              while(isalnum(cp[3])) cp++;
            }
function:   p=PRI_FUNC; cp+=l-1;
            goto operator;
          }
        for(l=0;isalnum(cp[l])||cp[l]=='\'';l++);
        if(cp[l]=='(') {
          op=(cp-term)+OP_USERF;
	  goto function;
        }
      }
      kn_stack[kn_sp++]=Neues_Blatt(cp,&cp);
      cp--;
    }
    else if(c==')')
      for(;;) {
        if(!op_sp) goto error;
        op=op_stack[--op_sp];
        if(op!=OP_OPEN) {if(!verwende(op)) goto error;}
        else break;
      }
    else if(strchr(chop,c)) {
      op=opnr(c); p=Pri(op);
      if(op==OP_SUB && (cp==term || cp[-1]=='(')) {
        op=OP_NEG;
        p=PRI_NEG;
      }
operator:
      while(op_sp) {
        op2=op_stack[op_sp-1];
        p2=Pri(op2);
        if(op2==OP_OPEN || p2<p || (p==PRI_FUNC || p==PRI_POT) && p2==p) break;
        --op_sp;
        if(!verwende(op2)) goto error;
      }
      op_stack[op_sp++]=op;
    }
    else goto error;
    cp++;
  }
  while(op_sp) {
    op2=op_stack[--op_sp];
    if(op2==OP_CLOSE) goto error;
    if(!verwende(op2)) goto error;
  }
  if(kn_sp!=1) goto error;
  return kn_stack[--kn_sp];
error:
  while(kn_sp) free(kn_stack[--kn_sp]);
  return NULL;
}

void Baum_abbauen(struct Knoten *k)
{
  if(k) {
    if(k->links) Baum_abbauen(k->links);
    if(k->rechts) Baum_abbauen(k->rechts);
    free(k);
  }
}

struct Knoten *Sinnlos(struct Knoten *k)
{
  if(!k->links && !k->rechts) {
    k->flags.is.K=0;
    k->op=OP_NONE; k->pri=PRI_NONE;
  }
  if(k->pri==PRI_MULDIV && k->flags.is.Konst && k->konst==0.) {
    Baum_abbauen(k);
    return Neue_Konst(0.);
  }
  if(k->op==OP_POT && k->rechts->flags.is.Konst && k->rechts->op==OP_NONE) {
    if(k->rechts->konst==0.) {
      Baum_abbauen(k);
      return Neue_Konst(1.);
    }
    if(k->rechts->konst==1.) {
      struct Knoten *n=k->links;
      k->links=NULL;
      Baum_abbauen(k);
      return Sinnlos(n);
    }
  }
  if(k->flags.is.Konst && k->links && !k->rechts && !k->links->links)
    if(k->konst==StdKonst(k->pri) || k->pri==PRI_MULDIV && k->konst==-1.) {
      struct Knoten *n=k->links->rechts;
      k->links->rechts=NULL;
      if(k->konst==-1.) Negiere(n);
      Baum_abbauen(k);
      return Sinnlos(n);
    }
  return k;
}

struct Knoten *verkette_Pot(struct Knoten *l,struct Knoten *r)
{
struct Knoten *k;
  if(r->op==OP_NONE && r->flags.is.Konst &&
     l->op==OP_NONE && l->flags.is.Konst) {
    l->konst=pow(l->konst,r->konst);
    Baum_abbauen(r); return l;
  }
  k=Neuer_Operator(OP_POT);
  k->links=l; k->rechts=r;
  return Sinnlos(k);
}

BOOL verwende(OP op)
{
struct Knoten *l,*r,*k;
  #define kn_pop(w) {if(kn_sp<=0) return FALSE;(w)=kn_stack[--kn_sp];}
  kn_pop(r);
  switch(Pri(op)) {
    case PRI_POT:
      kn_pop(l);
      k=verkette_Pot(l,r); break;
    case PRI_ADDSUB:
    case PRI_MULDIV:
      kn_pop(l);
      k=Verkette(l,op,r); break;
    case PRI_NEG: Negiere(k=r);break;
    case PRI_FUNC:
      k=Neuer_Operator(op);
      k->rechts=r; break;
  }
  kn_stack[kn_sp++]=k; return TRUE;
}

struct Knoten *Verkette(struct Knoten *l,OP op,struct Knoten *r)
{
OP kop=kommOp(op),nkop=nkommOp(op);
PRI pri=Pri(op);
struct Knoten *k,*o;
BOOL l_homogen=l->flags.is.Konst && l->op==OP_NONE || l->pri==pri;
BOOL r_homogen=r->flags.is.Konst && r->op==OP_NONE || r->pri==pri;
  if(op==OP_POT) return verkette_Pot(l,r);
  if(!r_homogen) {
    o=Neuer_Operator(op);
    if(l_homogen) {
      if(l->op==OP_NONE) {
        k=NeuerK(op);
        k->konst=l->konst;
        Baum_abbauen(l);
      }
      else k=l;
      o->rechts=r;
      k=Verschmelze(k,o);
    }
    else {
      struct Knoten *n=Neuer_Operator(kop);
      n->rechts=l; o->rechts=r;
      k=Verschmelze(NeuerK(op),n);
      k=Verschmelze(k,o);
    }
  }
  else {
    if(!l_homogen) {
      o=Neuer_Operator(op);
      if(r->op==OP_NONE) {
        k=NeuerK(op);
        k->konst=op==kop?r->konst:inv_konst(r->konst,pri);
        o->rechts=l; o->op=kop;
        k=Verschmelze(k,o);
        Baum_abbauen(r);
      }
      else {
        k=r;
        if(op==nkop) {
          inv_K(k,pri);
          o->op=kop;
        }
        o->rechts=l;
        k=Verschmelze(k,o);
      }
    }
    else {
      if(l->op==OP_NONE) {
        if(r->op==OP_NONE) {
          Rechne(k=l,op,r);
          Baum_abbauen(r);
        }
        else {
          k=r;
          if(op==nkop) inv_K(k,pri);
          Rechne(k,kop,l);
          Baum_abbauen(l);
        }
      }
      else {
        if(r->op==OP_NONE) {
          Rechne(k=l,op,r);
          Baum_abbauen(r);
        }
        else {
          Rechne(l,op,r);
          o=r->links;
          while(o) {
            k=o->links;
            o->links=NULL;
            if(op==nkop) o->op=nkop;
            l=Verschmelze(l,o);
            o=k;
          }
          o=r->rechts;
          while(o) {
            k=o->links;
            o->links=NULL;
            if(op==kop) o->op=nkop;
            l=Verschmelze(l,o);
            o=k;
          }
          r->links=r->rechts=NULL;
          Baum_abbauen(r); k=l;
        }
      }
    }
  }
  return Sinnlos(k);
}

struct Knoten *BaumKopie(struct Knoten *k)
{
struct Knoten *n=NULL;
  if(k) {
    n=Neuer_Operator(OP_NONE);
    *n=*k;
    n->links=BaumKopie(k->links);
    n->rechts=BaumKopie(k->rechts);
  }
  return n;
}

TreeCmp(const void *l,const void *r)
{
  Baum_zu_String((*(struct Knoten *const*)l)->rechts,Puffer3);
  Baum_zu_String((*(struct Knoten *const*)r)->rechts,Puffer4);
  return strcmp(Puffer3,Puffer4);
}

struct Knoten *sortK(struct Knoten *k)
{
void SortBaum(struct Knoten *);
struct Knoten *n,**nl;
int i,j;
  for(i=0,n=k;n;i++,n=n->links) SortBaum(n->rechts);
  if(i>1) {
    if(!(nl=(struct Knoten **)malloc(sizeof(n)*i))) {
      fprintf(stderr,"Speicher voll!\n");
      exit(10);
    }
    for(n=k,j=0;n;n=n->links,j++) nl[j]=n;
    qsort((void*)nl,i,sizeof(n),TreeCmp);
    for(k=n=*nl,j=1;j<i;n=n->links,j++) n->links=nl[j];
    n->links=NULL; free(nl);
  }
  return k;
}

void SortBaum(struct Knoten *k)
{
  if(!k) return;
  if(k->flags.is.K) {
    k->links=sortK(k->links);
    k->rechts=sortK(k->rechts);
  } else {
    SortBaum(k->links); SortBaum(k->rechts);
  }
}

void Wegen_NegPot(struct Knoten *o,struct Knoten *k)
{
  struct Knoten *n=o->rechts;
  if(n->op==OP_POT) {
    do n=n->rechts;
    while(n->op==OP_POT);
    if(n->op==OP_NONE && n->flags.is.Konst && n->konst<0.) {
      o->op=o->op==OP_MUL?OP_DIV:OP_MUL;
      n->konst=-n->konst;
      if(n->konst==1.)
	for(n=o;n->rechts && n->rechts->op==OP_POT;n=n->rechts)
	  n->rechts=Sinnlos(n->rechts);
    }
  }
  else if(n->flags.is.Neg) {
    n->flags.is.Neg=!n->flags.is.Neg;
    Negiere(k);
  }
}

void Wegen_NegVorz(struct Knoten *o)
{
  if(o->rechts->flags.is.Neg) {
    o->rechts->flags.is.Neg=0;
    o->op=o->op==OP_ADD?OP_SUB:OP_ADD;
  }
  else if(o->rechts->flags.is.Konst && (o->rechts->op==OP_NONE ||
        o->rechts->pri==PRI_MULDIV) && o->rechts->konst<0.) {
    o->rechts->konst=-o->rechts->konst;
    o->op=o->op==OP_ADD?OP_SUB:OP_ADD;
  }
}

struct Knoten *Ignoriere(struct Knoten *k,PRI pri)
{
  if(pri==PRI_ADDSUB && k->pri==PRI_MULDIV && !k->rechts && k->links &&
    !k->links->links && k->links->rechts)
      return k->links->rechts;
  else if(pri==PRI_MULDIV && k->op==OP_POT && k->rechts->op==OP_NONE &&
    k->rechts->flags.is.Konst)
      return k->links;
  return k;
}

char *SortB_String(struct Knoten *k,char *s)
{
  struct Knoten *cpy=BaumKopie(k);
  SortBaum(cpy); s=Baum_zu_String(cpy,s);
  Baum_abbauen(cpy); return s;
}

struct Knoten *Verschmelze(struct Knoten *k,struct Knoten *o)
{
OP kop;
struct Knoten *l,*r,*p1,*p2;
int v1=1,v2=1;
PRI pri=k->pri;
  if(!o) return k;
  kop=kommOp(o->op);
  if(o->pri==PRI_MULDIV) Wegen_NegPot(o,k);
  else Wegen_NegVorz(o);
  SortB_String(Ignoriere(o->rechts,pri),Puffer1);
  l=k->links; p1=NULL;
  while(l) {
    SortB_String(Ignoriere(l->rechts,pri),Puffer2);
    v1=strcmp(Puffer2,Puffer1);
    if(v1==0 || !l->links) break;
    p1=l; l=l->links;
  }
  r=k->rechts; p2=NULL;
  while(r) {
    SortB_String(Ignoriere(r->rechts,pri),Puffer2);
    v2=strcmp(Puffer2,Puffer1);
    if(v2==0 || !r->links) break;
    p2=r; r=r->links;
  }
  if(v1==0) k=Vereinfache(l,o,pri,k,p1,1);
  else if(v2==0) k=Vereinfache(r,o,pri,k,p2,2);
  else if(o->op==kop) {
    if(!l) l=k;
    o->links=l->links; l->links=o;
  } else {
    o->op=kop;
    if(r) {
      o->links=r->links; r->links=o;
    } else {
      o->links=k->rechts; k->rechts=o;
    }
  }
  return k;
}

struct Knoten *Vereinfache(struct Knoten *o1,struct Knoten *o2,PRI pri,
  struct Knoten *k,struct Knoten *p,int von)
{
struct Knoten *n,tmp;
OP op;
  tmp.konst=1.;
  if(pri==PRI_ADDSUB) {
    n=o1->rechts;
    if(n->pri!=PRI_MULDIV) {
      n=NeuerK(OP_MUL);
      n->links=Neuer_Operator(OP_MUL);
      n->links->rechts=o1->rechts;
      o1->rechts=n;
    }
    op=o2->op;
    if(von==2) op=op==OP_ADD?OP_SUB:OP_ADD;
    if(o2->rechts->pri==PRI_MULDIV)
      Rechne(n,op,o2->rechts);
    else Rechne(n,op,&tmp);
    Baum_abbauen(o2);
    if(p) p->links=o1->links;
    else if(von==1) k->links=o1->links;
    else k->rechts=o1->links;
    o1->links=NULL;
    if(von==2) o1->op=OP_SUB;
  }
  else if(pri==PRI_MULDIV) {
    if(o1->rechts->op!=OP_POT || o1->rechts->rechts->flags.is.Konst==0
      || o1->rechts->rechts->op!=OP_NONE) {
      n=Neuer_Operator(OP_POT);
      n->rechts=Neue_Konst(1.);
      n->links=o1->rechts;
      o1->rechts=n;
    }
    else n=o1->rechts;
    op=o2->op==OP_MUL?OP_ADD:OP_SUB;
    if(von==2) op=op==OP_ADD?OP_SUB:OP_ADD;
    if(o2->rechts->op==OP_POT && o2->rechts->rechts->flags.is.Konst &&
      o2->rechts->rechts->op==OP_NONE)
      Rechne(n->rechts,op,o2->rechts->rechts);
    else Rechne(n->rechts,op,&tmp);
    Baum_abbauen(o2);
    if(p) p->links=o1->links;
    else if(von==1) k->links=o1->links;
    else k->rechts=o1->links;
    o1->links=NULL;
    if(von==2) o1->op=OP_DIV;
  }
  o1->rechts=Sinnlos(o1->rechts);
  if(o1->rechts->op==OP_NONE && o1->rechts->flags.is.Konst)
    if(pri==PRI_ADDSUB && o1->rechts->konst==0 ||
      pri==PRI_MULDIV && o1->rechts->konst==1.) {
      Baum_abbauen(o1);
      o1=NULL;
    }
  k=Verschmelze(k,o1);
  return Sinnlos(k);
}

BOOL dop_klammer(char **sp)
{
  return (*sp!=Beginn && (*sp)[-1]!='(')?((*sp)++[0]='(',TRUE):FALSE;
}

BOOL pri_klammer(struct Knoten *v,struct Knoten *s,char **sp)
{
  return (v->pri>s->pri && s->pri!=PRI_NONE || (v->pri==s->pri || s->pri==PRI_FUNC) && v->pri==PRI_POT || v->op==OP_USERF)?\
    ((*sp)++[0]='(',TRUE):FALSE;
}

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

char *cut(char *s)
{
char *cp=s;
  do;while(*--cp=='0');
  if(isdigit(*cp)) s=cp+1;
  else if(*cp=='.') s=cp;
  *s=0; return s;
}

char *Baum_zu_String(struct Knoten *k,char *s)
{
  if(k) s=Baum_String(k,Beginn=s);
  else *s++='0';
  *s=0; return s;
}

char *Baum_String(struct Knoten *k,char *s)
{
int i;
  if(k->op==OP_NONE) {
    if(k->flags.is.Konst) {
      sprintf(s,"%lf",k->konst);
      s=cut(strchr(s,0));
    }
    else if(k->flags.is.Neg) {
      BOOL kl=dop_klammer(&s);
      *s++='-';
      strncpy(s,k->term,k->len); s+=k->len;
      klammer_zu(&s,kl);
    }
    else {
      strncpy(s,k->term,k->len); s+=k->len;
    }
    return s;
  }
  if(k->op>=OP_FUNC1) {
    BOOL kl1,kl2;
    if(k->flags.is.Neg) {
      kl1=dop_klammer(&s);
      *s++='-';
    }
    strncpy(s,k->term,k->len);
    s+=k->len;
    for(i=0;i<k->primes;i++) *s++='\'';
    kl2=pri_klammer(k,k->rechts,&s);
    if(!kl2) *s++=' ';
    s=Baum_String(k->rechts,s);
    klammer_zu(&s,kl2);
    if(k->flags.is.Neg) klammer_zu(&s,kl1);
    return s;
  }
  if(k->op==OP_POT) {
    BOOL kl1,kl2;
    if(k->flags.is.Neg) {
      kl1=dop_klammer(&s);
      *s++='-';
    }
    kl2=pri_klammer(k,k->links,&s);
    s=Baum_String(k->links,s);
    klammer_zu(&s,kl2);
    *s++='^';
    kl2=pri_klammer(k,k->rechts,&s);
    s=Baum_String(k->rechts,s);
    klammer_zu(&s,kl2);
    if(k->flags.is.Neg) klammer_zu(&s,kl1);
    return s;
  }
  if(k->flags.is.K) {
    BOOL noop=FALSE,kl1,kl2;
    struct Knoten *n;
    if(k->flags.is.Konst && k->konst!=StdKonst(k->pri)) {
      if(k->konst<0.) kl1=dop_klammer(&s);
      sprintf(s,"%lf",k->konst);
      s=cut(strchr(s,0));
      if(k->konst<0.) klammer_zu(&s,kl1);
    }
    else if(k->links==NULL) {
      if(k->pri==PRI_MULDIV) *s++='1';
    }
    else noop=TRUE;
    n=k->links;
    while(n) {
      if(!noop) *s++=*Op(n->op);
      else noop=FALSE;
      kl2=pri_klammer(n,n->rechts,&s);
      s=Baum_String(n->rechts,s);
      klammer_zu(&s,kl2);
      n=n->links;
    }
    n=k->rechts;
    if(n) {
      *s++=*Op(k->op);
      noop=TRUE;
      if(n->links) *s++='(';
      while(n) {
        if(!noop) *s++=*Op(n->op);
        else noop=FALSE;
        kl2=pri_klammer(n,n->rechts,&s);
        s=Baum_String(n->rechts,s);
        klammer_zu(&s,kl2);
        n=n->links;
      }
      if(k->rechts->links) *s++=')';
    }
  }
  return s;
}

#define WIDTH 60
struct node {
  struct node *prev,*next;
  char s[WIDTH+1];
};
struct list {
  struct node *first,*last;
};

struct Knoten *u,*v,*a,*b,*K,*D;
char s1[20],s2[20],*muster,
*dMul[3]={"*ub","*va","+*av*bu"},
*dDiv[3]={"/_*ub^v2","/av","/-*av*bu^v2"},
*dPot[3]={"*^uv*#01ub","*v*^u-v1a","*^uv+*b#01u*/vua"},
*dFunk[]={"/bv","*#03vb","*#02vb","*#05vb","*_#04vb",
"/b^#03v2","_/b^#02v2","/b^#05v2","_/b^#04v2","*/bv#10e",
"/b#15-1^v2","_/b#15-1^v2","/b+1^v2","_/b+1^v2","/b*2#15v",
"/b#15+1^v2","/b#15-^v21","/b-1^v2","/b-1^v2","*b#20v"};
char *PotMsg1[3]={
"Bei &k ist die Basis &u konstant. Man verfährt wie folgt: "
"(c^v)'=ln c*c^v*v', mit c=&u und v=&v.",
"&k ist ein Term mit konstanter Potenz &v. Die Basis b ist &u. "
"Solche Terme differenziert man so: (b^c)'=c*b^(c-1)*b'.",
"Bei &k sind weder die Basis u=&u noch v=&v konstant. Man differenziert "
"Ausdrücke dieser Art folgendermaßen: (u^v)'=u^v*(v'*ln u+v*u'/u)."},
*PotMsg2[2]={"Differenzieren wir also einmal v.",
"Berechnen wir also die Ableitung der Basis b."},
*PotMsg3[3]={"Mit c=&u, v=&v und v'=&b wird &k nach (c^v)'=ln c*c^v*v' zu &d.",
"Damit wird &k nach (b^c)'=c*b^(c-1)*b' zu &d.",
"Mit u=&u, v=&v, u'=&a und v'=&b ergibt sich nach "
"(u^v)'=u^v*(v'*ln u+v*u'/u) aus &k das Ergebnis &d."},
*PotMsg4[2]={"v' ist dabei 1, &k wird also zu &d.",
"b' ist natürlich 1 und so erhalten wir &d."},
*ASMsg[3]={"Terme, die durch + oder - getrennt sind, werden einzeln "
"differenziert und anschließend wieder zusammengesetzt.",
"Die Konstante &# wird beim Differenzieren zu 0, wir müssen also"
" nur den Rest ableiten.","Da wir ja &k zu differenzieren"
" hatten, dürfen wir natürlich nicht auf das Minus vergessen"
" und erhalten deshalb &d."},
*MDMsg[5]={"Bei einer Division kommt die Quotientenregel "
"(u/v)'=(u'*v-v'*u)/v^2 zum Einsatz. Hier ist u=&# eine Konstante"
", die Ableitung u' also 0. Wir differenzieren also nach -v'*u"
"/v^2, mit v=&v.","Damit erhalten wir für &k nach -v'*c/v^2 mit v=&v"
" und v'=&b schlußendlich &d.","Der konstante Faktor &# bleibt"
" beim Differenzieren unverändert, wir differenzieren also erst"
" einmal den Rest.","Wir haben bei &k eine Division von u=&u durch"
" v=&v. Hier gilt die Quotientenregel (u/v)'=(u'*v-v'*u)/v^2.",
"Mit u=&u, v=&v, u'=&a und v'=&b wird &k nach der Quotientenregel"
" (u/v)'=(u'*v-v'*u)/v^2 zu &d."},
*MMsg[2]={"Bei einem Produkt zweier Terme u=&u und v=&v kommt"
" die Produktregel (u*v)'=u'*v+v'*u zum Einsatz.",
"Mit u=&u, v=&v, u'=&a und v'=&b ergibt sich nach (u*v)'="
"u'*v+v'*u aus &k eben &d."};

struct node *new_node(struct list *l)
{
  struct node *n=malloc(sizeof(struct node));
  if(n==NULL) {
    fprintf(stderr,"Speicher voll!\n");
    exit(10);
  }
  n->prev=n->next=NULL;
  if(l->first) {
    l->last->next=n;
    n->prev=l->last;
    l->last=n;
  }
  else l->first=l->last=n;
  return n;
}

void behandle(char *src,char *dest)
{
char c;
  while((c=*src++)!=0)
    if(c!='&') *dest++=c;
    else switch(*src++) {
      case 'a': dest=Baum_zu_String(a,dest);break;
      case 'b': dest=Baum_zu_String(b,dest);break;
      case 'u': dest=Baum_zu_String(u,dest);break;
      case 'v': dest=Baum_zu_String(v,dest);break;
      case 'k': dest=Baum_zu_String(K,dest);break;
      case 'd': dest=Baum_zu_String(D,dest);break;
      case '1': strcpy(dest,s1);dest+=strlen(s1);break;
      case '2': strcpy(dest,s2);dest+=strlen(s2);break;
      case '#': sprintf(dest,"%lf",K->konst);
        dest=cut(strchr(dest,0));break;
    }
  *dest=0;
}

void Schreibe(struct list *l,char *s)
{
static char um[]={" =+-*^/"};
struct node *n=new_node(l);
  if(strlen(s)<=WIDTH) strcpy(n->s,s);
  else {
    int i=WIDTH+1;
    while(--i>0) if(strchr(um,s[i])) break;
    if(i<0) i=WIDTH;
    else i++;
    strncpy(n->s,s,i);
    n->s[s[i-1]!=' '?i--:i-1]=0;
    Schreibe(l,s+i);
  }
}

void Ausgabe(struct list *l,char *s)
{
  behandle(s,Puffer1); Schreibe(l,Puffer1);
}

void anhaengen(struct list *l,struct list *r)
{
  if(!l->first) *l=*r;
  else if(r->first) {
    l->last->next=r->first;
    r->first->prev=l->last;
    l->last=r->last;
  }
}

void Loesche(struct list *l)
{
struct node *n=l->first,*m;
  while(n) {
    m=n; n=n->next; free(m);
  }
}

void beide_abl(struct list *l,struct list *r,struct list *li)
{
  if(X(u)) {
    Ausgabe(li,"Da u=x, ist u'=1. Berechnen wir also die Ableitung von v=&v.");
    Loesche(l);
    anhaengen(li,r);
  }
  else if(X(v)) {
    Ausgabe(li,"Da v=x, ist v'=1. Berechnen wir also die Ableitung von u=&u.");
    Loesche(r);
    anhaengen(li,l);
  }
  else {
    Ausgabe(li,"Berechnen wir zuerst einmal u'.");
    anhaengen(li,l);
	 Ausgabe(li,"Für &k brauchen wir noch die Ableitung von v=&v.");
    anhaengen(li,r);
  }
}

Art(void)
{
  int art=2;
  if(!a || a->op==OP_NONE && a->flags.is.Konst && a->konst==0.) {
    Baum_abbauen(a); a=NULL;
    art-=2;
  }
  if(!b || b->op==OP_NONE && b->flags.is.Konst && b->konst==0.) {
    Baum_abbauen(b); b=NULL;
    art--;
  }
  return art;
}

struct Knoten *diffAdd(struct Knoten *k,struct list *li)
{
struct Knoten *l,*r;
  if(k) {
    r=Differenziere(k->rechts,li);
    l=diffAdd(k->links,li);
    if(l) r=Verkette(l,OP_ADD,r);
    return r;
  }
  return NULL;
}

struct Knoten *diffMul(struct Knoten *k,struct list *li)
{
struct Knoten *l,*r;
int art;
struct list ll,rl;
  if(k) {
    ll.first=rl.first=NULL;
    r=Differenziere(k->rechts,&ll);
    l=diffMul(k->links,&rl);
    if(!l) {
      anhaengen(li,&ll);Loesche(&rl);
      return r;
    }
    v=NeuerK(OP_MUL);
    v->links=BaumKopie(k->links);
    v=Sinnlos(v);
    u=k->rechts;
    b=l; a=r; art=Art();
    if(art<0) return Neue_Konst(0.);
    muster=dMul[art];
    D=l=Sinnlos(Regeln());
    K=NeuerK(OP_MUL);
    K->links=k;
    Ausgabe(li,MMsg[0]);
    beide_abl(&ll,&rl,li);
    Ausgabe(li,MMsg[1]);
    K->links=NULL;
    Baum_abbauen(K); Baum_abbauen(v);
    Baum_abbauen(a); Baum_abbauen(b);
    return l;
  }
  return NULL;
}

struct Knoten *Regeln(void)
{
struct Knoten *k;
int d;
  switch(d=*muster++) {
    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 '_': Negiere(k=Regeln());break;
    case 'e': k=Neues_Blatt("e",&cp);break;
    case '#':
      sscanf(muster,"%d",&d);
      muster+=2;
      k=Neuer_Operator(d+OP_FUNC1-1);
      if(d==10) {k->term=K->term;k->len=K->len;}
      k->rechts=Regeln();
      break;
    default:
      if(isdigit(d)) k=Neue_Konst((double)(d-'0'));
      else {
        k=Regeln();
        k=Verkette(k,opnr(d),Regeln());
      }
  }
  return k;
}

struct Knoten *Differenziere(struct Knoten *k,struct list *li)
{
struct Knoten *d;
int art;
struct list ll,rl;
  ll.first=rl.first=NULL; K=k;
  if(k->op==OP_NONE) {
    if(k->flags.is.Konst==0 && k->len==1 && *k->term=='x') {
      Ausgabe(li,"x abgeleitet ergibt 1.");
      return Neue_Konst(k->flags.is.Neg?-1.:1.);
    }
    Ausgabe(li,"Die Konstante &k abgeleitet ergibt 0.");
    return Neue_Konst(0.);
  }
  if(k->op>=OP_FUNC1) {
    if(C(k->rechts)) {
      Ausgabe(li,"&k ist konstant, die Ableitung davon also 0.");
      Loesche(&rl);
      return Neue_Konst(0.);
    }
    b=Differenziere(k->rechts,&rl);
    v=k->rechts;
    if(k->op>=OP_USERF) {
      u=BaumKopie(k);
      u->primes++; muster="*ub";
    }
    else muster=dFunk[k->op-OP_FUNC1];
    K=k; d=Regeln();
    if(k->op>=OP_USERF) Baum_abbauen(u);
    if(k->flags.is.Neg) Negiere(d);
    d=D=Sinnlos(d); K=k;
    strncpy(s1,k->term,k->len);
    strcpy(s1+k->len," z");
    if(!X(v)) {
      if(k->op>=OP_USERF) Ausgabe(li,"Leiten wir die Funktion &k ab und multiplizieren wir sie mit der inneren Ableitung z'. Das Argument z ist &v.");
      else {
        strcpy(s2,FunkMsg[k->op-OP_FUNC1]);
        Ausgabe(li,"Allgemein wird eine Funktion &1 beim Differenzieren zu &2. Hier ist z=&v.");
      }
      Ausgabe(li,"Berechnen wir die Ableitung davon.");
      anhaengen(li,&rl);
      if(k->op>=OP_USERF) Ausgabe(li,"Die Ableitung von &k ist also &d.");
      else Ausgabe(li,"Wir bekommen also aus &1=&k nach der Vorschrift (&1)'=&2 als Ergebnis &d.");
    }
    else {
      Ausgabe(li,"Die Funktion &k abgeleitet wird zu &d.");
      Loesche(&rl);
    }
    Baum_abbauen(b);
    return d;
  }
  if(k->op==OP_POT) {
    d=Differenziere(k->links,&ll);
    b=Differenziere(k->rechts,&rl);
    a=d;
    u=BaumKopie(k->links);
    v=BaumKopie(k->rechts);
    if((art=Art())<0) {
      Ausgabe(li,"&k ist konstant, die Ableitung also 0.");
      Loesche(&ll);Loesche(&rl);
      return Neue_Konst(0.);
    }
    muster=dPot[art];
    d=Regeln();
    if(k->flags.is.Neg) Negiere(d);
    D=d=Sinnlos(d); K=k;
    Ausgabe(li,PotMsg1[art]);
    if(art<2) {
      if(!X(u) && !X(v)) {
        Ausgabe(li,PotMsg2[art]);
        anhaengen(li,art?&ll:&rl);
        Ausgabe(li,PotMsg3[art]);
        Loesche(art?&rl:&ll);
      }
      else {
        Loesche(&ll);Loesche(&rl);
        Ausgabe(li,PotMsg4[art]);
      }
    }
    else {
      if(X(u) && X(v)) {
        Ausgabe(li,"Da u und v=x, sind sowohl u' als auch v'=1.");
        Loesche(&ll); Loesche(&rl);
      }
      else beide_abl(&ll,&rl,li);
      Ausgabe(li,PotMsg3[2]);
    }
    Baum_abbauen(u); Baum_abbauen(v);
    Baum_abbauen(a); Baum_abbauen(b);
    return d;
  }
  if(k->pri==PRI_ADDSUB) {
    struct Knoten *l,*r;
    BOOL einfach=k->links && !k->rechts && !k->links->links ||
      k->rechts && !k->links && !k->rechts->links;
    if(!einfach) Ausgabe(li,ASMsg[0]);
    if(k->flags.is.Konst && k->konst!=0.) Ausgabe(li,ASMsg[1]);
    l=diffAdd(k->links,li);
    r=diffAdd(k->rechts,li);
    if(!l) Negiere(d=r);
    else if(!r) d=l;
    else d=Verkette(l,OP_SUB,r);
    D=d=Sinnlos(d); K=k;
    if(!einfach)
      Ausgabe(li,"&k differenziert ergibt also &d.");
    else if(!k->links) Ausgabe(li,ASMsg[2]);
    return d;
  }
  d=diffMul(k->links,&ll);
  if(k->rechts) {
    b=diffMul(k->rechts,&rl); a=d;
    u=NeuerK(OP_MUL);
    if(!k->links) u->konst=k->konst;
    else u->links=BaumKopie(k->links);
    u=Sinnlos(u);
    v=NeuerK(OP_MUL);
    v->links=BaumKopie(k->rechts);
    v=Sinnlos(v);
    if((art=Art())<0) return Neue_Konst(0.);
    muster=dDiv[art];
    d=Regeln();
  }
  if(k->links && k->flags.is.Konst && k->konst!=1.)
    d=Verkette(d,OP_MUL,Neue_Konst(k->konst));
  d=D=Sinnlos(d);
  K=k;
  if(!k->links) {
    Ausgabe(li,MDMsg[0]);
    if(!X(v)) {
      Ausgabe(li,"Wir berechnen also einmal die Ableitung von &v.");
      anhaengen(li,&rl);
      Ausgabe(li,MDMsg[1]);
    }
    else {
		Ausgabe(li,"v' ist natürlich 1 und wir erhalten &d.");
      Loesche(&rl);
    }
  }
  else {
    BOOL ko=k->flags.is.Konst && k->konst!=1.;
    if(ko) Ausgabe(li,MDMsg[2]);
    if(k->rechts) {
      Ausgabe(li,MDMsg[3]);
      beide_abl(&ll,&rl,li);
      Ausgabe(li,MDMsg[4]);
      if(ko) Ausgabe(li,"Dabei wurde noch mit der Konstanten &# multipliziert.");
    }
    else {
      anhaengen(li,&ll);
      if(ko) Ausgabe(li,"Als Ergebnis von &k erhalten wir also &d.");
    }
  }
  if(k->rechts) {
    Baum_abbauen(u); Baum_abbauen(v);
    Baum_abbauen(a); Baum_abbauen(b);
  }
  return d;
}

void diff(char *formel,struct list *l)
{
  errno=0;
  if(Term_korrekt(formel) && (K=Root=Baum_aufbauen(formel)) && errno==0) {
    Ausgabe(l,"Angabe: &k");
    D=Differenziere(Root,l);
    Ausgabe(l,"Endergebnis: &d");
    Baum_abbauen(D);
    Baum_abbauen(Root);
  }
  else Ausgabe(l,"Angabe fehlerhaft!");
}

struct IntuitionBase *IntuitionBase;
struct GfxBase *GfxBase;
struct Window *w;
struct RastPort *rp;
UBYTE Formel[256],AlteFormel[256],Kopie[256];
struct StringInfo si_Eingabe={Formel,AlteFormel,0,256};
struct Gadget gg_Eingabe={
NULL,20,25,520,11,GADGHCOMP,RELVERIFY,
STRGADGET,NULL,NULL,NULL,0,(APTR)&si_Eingabe,1,NULL};
struct NewWindow nw={
10,10,560,160,0,1,
GADGETUP|CLOSEWINDOW|RAWKEY,
WINDOWDRAG|WINDOWCLOSE|WINDOWDEPTH|ACTIVATE,&gg_Eingabe,
NULL,(UBYTE *)"How-To-Derive ...  1992 by Markus Öllinger  (c) by M&T",
NULL,NULL,0,0,0,0,WBENCHSCREEN};

void Male(long x,long y,int w,char *t)
{
  SetDrMd(rp,JAM1);
  x=x+(w>>1)-(strlen(t)<<2);
  SetAPen(rp,2);Move(rp,x+1,y+7);
  Text(rp,t,(long)strlen(t));
  SetAPen(rp,1);Move(rp,x,y+6);
  Text(rp,t,(long)strlen(t));
}

void ende(int err)
{
  if(w) CloseWindow(w);
  if(GfxBase) CloseLibrary((struct Library *)GfxBase);
  if(IntuitionBase) CloseLibrary((struct Library *)IntuitionBase);
}

void init(void)
{
  atexit(ende);
  if(!(IntuitionBase=(struct IntuitionBase *)OpenLibrary("intuition.library",33)))
    exit(1);
  if(!(GfxBase=(struct GfxBase *)OpenLibrary("graphics.library",33)))
    exit(1);
  if(!(w=OpenWindow(&nw))) exit(2);
  rp=w->RPort;
  SetRast(rp,3); RefreshWindowFrame(w);
  SetAPen(rp,0); RectFill(rp,20,50,540,145);
  ActivateGadget(&gg_Eingabe,w,NULL);
  Male(0,15,560,"Angabe  f(x)=?");
  Male(0,40,560,"Lösungsweg");
}

void Zeige(struct node *n,long scroll,int s,int e)
{
int i;
  SetAPen(rp,1); SetBPen(rp,0);
  if(scroll) ScrollRaster(rp,0,scroll,20,50,540,145);
  for(i=0;n && i<e;n=n->next,i++) if(i>=s) {
    Move(rp,20,(long)(56+(i<<3)));
    Text(rp,n->s,(long)strlen(n->s));
  }
}

void main(int argc,char **argv)
{
struct IntuiMessage *msg;
ULONG class; USHORT code;
struct list l;
struct node *show=l.first=NULL;
  init();
  do {
    WaitPort(w->UserPort);
    msg=(struct IntuiMessage *)GetMsg(w->UserPort);
    class=msg->Class; code=msg->Code;
    ReplyMsg((struct Message *)msg);
    if(class==GADGETUP) {
      Loesche(&l); l.first=NULL;
      diff(strcpy(Kopie,Formel),&l);
      SetAPen(rp,0); RectFill(rp,20,50,540,145);
      Zeige(show=l.first,0,0,12);
    }
    else if(class==RAWKEY) {
      if(code==0x4c && show->prev) Zeige(show=show->prev,-8,0,1);
      else if(code==0x4d && show->next) Zeige(show=show->next,8,11,12);
      else if(code==0x45) break;
      else if(code==0x44) ActivateGadget(&gg_Eingabe,w,NULL);
    }
  } while(class!=CLOSEWINDOW);
  Loesche(&l);
  exit(0);
}