/***************************************************************************
*                                                                          *
*   Fachhochschule Koeln                                 Matthias Gross    *
*   Nachrichtentechnik                                          SS 1998    *
*                                                                          *
*   Demo-Programm fuer den Aufbau eines Syntaxbaumes                       *
*                                                                          *
*   Das Header-File enthaelt                                               *
*     #include                                                             *
*     #defines                                                             *
*     Strukturen                                                           *
*     Datentyp-Definitionen                                                *
*     Funktionsprototypen                                                  *
*                                                                          *
***************************************************************************/

#include <stdio.h>                  /* Standard-Includes vornehmen        */
#include <stdlib.h>                 /* Standard-Includes vornehmen        */
#include <string.h>                 /* fuer strlen() etc.                 */
#include <ctype.h>                  /* fuer isdigit()                     */
#include <math.h>                   /* fuer pow()                         */

/* Die Struktur eines Knotens fuer den binaeren Syntax-Baum
*/
typedef
  struct sMathNode
  {
    struct sMathNode  *left,    /* Linker und rechter Nachfolger          */
                      *right;   /* NULL falls keine Nachfolger            */
    char              Op;       /* Der Operator an dieser Stelle im Baum
                                   Ist Op ='\0' ist es ein Blatt          */
    double            Wert;     /* Der dort ggfs. abgelegte Zahlenwert    */
    char              *Text;    /* Der Input-String an dieser Stelle des Baum
                                   Der Variablenname, falls eine Variable
                                   dort steht NULL, falls das Blatt nur
                                   eine Zahl enthaelt*/
  } MathNode;

int StrAnalyse(char *str);
/* Diese Routine liefert zurueck:
     1 falls str eine Zahl ist,
     0 falls unbekannt
*/

char *StrFindEK(char *str);
/* Die Routine findet im String str zu einer oeffnenden Klammer ( an
   der ersten Position des Strings die Position der passenden schliessenden Klammer )
   Liefert NULL, falls String fehlerhaft ist.
*/

char *StrClean(char *str);
/* Entfernt bei einem String fuehrende und anhaengende Luecken
   und entfernt ggfs. ueberfluessige Klammern am Ende und Beginn.
   Diese Funktion wird an Ort und Stelle im Speicher durchgefuehrt.
   Liefert NULL, falls String zusammengesetzt ist.
   Die Routine wird rekursiv verwendet.
*/

MathNode *NewNode(char *str);
/* Neues Knotenelement mit dem Inhalt str generieren.
   Es wird entsprechender Platz angefordert und str ggfs umkopiert
   oder math. korrekt eingesetzt.
   Falls Routine scheitert, wird NULL zurueckgegeben.
*/

MathNode *DelTree(MathNode *MN);
/* Loescht den gesamten Teilbaum auf den MN zeigt und liefert NULL zurueck.
*/

MathNode *SetWert(MathNode *MN, double w);
/* Setzt Knoten MN auf Wert w und loescht anhaengenden
   linken und rechten Teilbaum.
   (Dies wird beim Kuerzen des Baums verwendet)
*/

MathNode *SimplifyTree(MathNode *MN);
/* Vereinfacht den eingegebenen Syntaxbaum mit der Wurzel MN
   z.Z. werden hier beruecksichtigt:
-  Zusammenfassen von Zahlen bei +, -, *, /, ^
-  0 + ? wird zu ?
-  0 * ?, 0 / ?, 0 ^ ? wird zu 0
-  1 * ? = ?, 1 ^ ? = 1
*/

MathNode *SplitNode(MathNode *MN);
/* Splittet den vorhandenen Baum im Praeorderverfahren auf
*/

void OutputInfixKlammer(MathNode *MN, char Op)
/* Ausgabe des Baums in Inorder-Technik (Infix-Notation) mit korrekter Klammerung.
   Op ist der Operator des uebergeordneten Knotens
*/