Logischen Ausdruck normalisieren

[SonjaB]

Hallo, ich habe diese Frage bereits in einem anderen Forum gestellt. Leider konnte oder wollte mir dort niemand helfen und es kam nur Spott.
Eine kleine Bitte, ich weiss, dass hier auch Spotlight-Benutzer mitlesen. Ich möchte euch bitten, die Hetzkampagne gegen mich nicht hier fortzusetzen.

Nun zur Aufgabe:

Es soll ein Programm geschrieben werden, das einen logischen Ausdruck als Klartext einliest, diesen vereinfacht und die vereinfachte Darstellung als Klartext ausgibt.
Dabei sollen Variablen als logische Eingangswerte des Ausdrucks akzeptiert werden.
Der eingegebene Ausdruck soll in eine eine optimale disjunktive oder konjunktive Normalform überführt werden.
Als Operatoren sollen && (AND), || (OR) und ! (NEGATION) sowie Klammerebenen erlaubt sein. Die Auswertung soll nach der in C üblichen Reihenfolge erfolgen.

Hey, was will dieser Mensch von mir? Mehr Informationen habe ich leider nicht

Ich wäre sehr froh, wenn hier im Forum hilfreichere Antworten als in Spotlight kämen.

Danke,
Sonja

[Gast]

Hmm,

vermutlich soll dein Programm erst die Wörter wie "AND"... einlesen und in dann erstmal vereinfachen:
Also aus "NOT NOT X" wird dann einfach X. Weils sich "wegkürzt".

Zum Schluss soll das Programm dann die Wörter mit den C-Zeichen ersetzen.
(Aus NOT wird dann !)

Auf jeden Fall wirst du eine Liste mit der richtigen Reihefolge haben müssen:
http://www.physik.tu-berlin.de/~dschm/scri/ckurs/node22.html

[borg]

Literal: a oder !a
Klausel: K1 || K2 || K3 || ... || Kn, wobei K ein Literal ist
Monom: M1 && M2 && M3 && ... && Mn, wobei M ein Literal ist
Negations-Normalform(NNF): "!" nur in Literalen
Konjunktive-Normalform(KNF): K1 && K2 && ... && Kn, wobei K eine Klausel ist und der Ausdruck ist in NNF
Disjunktive-Normalform(DNF): M1 || M2 || ... || Mn, wobei M ein Monom ist und der Ausdruck ist in NNF

das zu lösen ist gar nicht ganz so trivial, aber die aufgabenstellung sollte klar sein oder?

[Bashar]

SonjaB schrieb:

Nun zur Aufgabe:

Es soll ein Programm geschrieben werden, das einen logischen Ausdruck als Klartext einliest, diesen vereinfacht und die vereinfachte Darstellung als Klartext ausgibt.
Dabei sollen Variablen als logische Eingangswerte des Ausdrucks akzeptiert werden.
Der eingegebene Ausdruck soll in eine eine optimale disjunktive oder konjunktive Normalform überführt werden.
Als Operatoren sollen && (AND), || (OR) und ! (NEGATION) sowie Klammerebenen erlaubt sein. Die Auswertung soll nach der in C üblichen Reihenfolge erfolgen.

Hey, was will dieser Mensch von mir? Mehr Informationen habe ich leider nicht

Was genau verstehst du denn nicht? Ein Teil der Aufgabe beinhaltet, einen String zu parsen. Schonmal von gehört? Dann sollst du eine boolesche Funktion minimieren und in KNF oder DNF ausgeben. Du klingst, als hättest du davon noch nie was gehört. Oder doch? Bitte hier nicht das unwissende Baby spielen, das an die Hand genommen werden will -- denn wenn du schon mit den Begriffen nichts anfangen kannst, frag ich mich, wie du zu der Ehre kommst, diese Aufgabe bearbeiten zu dürfen ... denn du bist unter den Umständen definitiv nicht in der Lage, sie zu lösen.

[MG80S]

Das ist aber allerdings sooo trivial nicht. Dürfen Operatoren mehrmals im Ausdruck vorkommen? Dann wirds heavy. Ansonsten ist es ja mehr ein "Ausklammer"-Prinzip.

[Taurin]

Ich würde den eingegebenen Ausdruck parsen, Wertetabelle erstellen, und dann den Algorithmus von Quine-MyClusky anweden. Als Ergebnis erhällst du die minimale DNF der Eingabe. Die Schritte sind aber nicht unbedingt trivial, insbesondere, da du nichtmal die Aufgabe verstehst. Wie kommst du denn zu der Ehre, diese Aufgabe lösen zu dürfen?

[SonjaB]

Hallo, die "Ehre" kommt von meinem Lehrer. Ich mache gerade eine Weiterbildung zur Fachinformatikerin und bin in einem sechsmonatigen C Kurs. Ausgesucht habe ich mir das wirklich nicht und unser Lehrer quält uns ständig mit neuen verrückten Aufgaben
Aber danke für eure Antworten. Es würde mich freuen, wenn ihr mir auch noch ein konkretes Beispiel hättet.

M.f.G.
Sonja

[Power Off]

SonjaB: Besorg Dir mal das Buch "Compilers" von Aho / Sethi / Ullman, erschienen im Addison-Wesley-Verlag. Wenn Du Englisch kannst, nimm das Original, sonst die Uebersetzung. Du kannst es Dir bestimmt auch irgendwo ausleihen, aber wenn Du mal als Programmiererin arbeiten willst, lohnt es sich u.U. auch, das Buch zu kaufen.

Was Du machen musst, ist zunaechst eine Syntax der Sprache zu definieren, die Du haben willst. Dafuer eignet sich sehr gut EBNF, die von Niklaus Wirth (an der ETH Zuerich) entwickelt wurde. " { ... } " bedeutet "0 oder mehrere des eingeschlossenen Ausdrucks", " [ ... ] " bedeutet "ein optionaler Ausdruck", " | " bedeutet "oder".

Fuer einfache Ausdruecke koennte das in etwa so aussehen (ich benutze meist eine erweiterte Form der EBNF mit Regular Expressions):

zahlenwert := /[0-9]+/ .
variablenname := /[a-zA-Z_][a-zA-Z0-9_]+/ .
basis-ausdruck := zahlenwert | variablenname | '(' ausdruck ')' .
unaerer-ausdruck := [ '-' ] basis-ausdruck .
multiplikations-ausdruck := unaerer-ausdruck { ( '*' | '/' | '%' ) unaerer-ausdruck } .
additions-ausdruck := multiplikations-ausdruck { ( '+' | '-' ) multiplikations-ausdruck } .
vergleichs-ausdruck := additions-ausdruck [ ( '==' | '!=' | '>=' | '<=' | '<' | '>' ) additions-ausdruck ] .
und-ausdruck := vergleichs-ausdruck { '&&' vergleichs-ausdruck } .
oder-ausdruck := und-ausdruck { '||' und-ausdruck } .
ausdruck := oder-ausdruck .

Damit kann man im Prinzip schon den Programmcode schreiben. Am besten ist, man erzeugt zunaechst einen Syntaxbaum.

Leider hab ich jetzt nicht die Zeit, das zu machen (ist eigentlich gar nicht so schwer), hier erstmal ein Programmtext, den ich neulich fuer jemand anderen mit einem aehnlichen Problem geschrieben habe:

(Ist allerdings C++, sorry)

#include <string>
#include <math.h>
#include <stdio.h>

// EBNF fuer Eval:
//
// number := /[0-9]+\.?[0-9]*[eE]?[+-]?[0-9]*/ ;
// func := 'sqrt' .
//
// base-expr := number | '(' expr ')' | func '(' expr ')' .
// unary-expr := [ '-' ] base-expr .
// mult-expr := unary-expr { ( '**' | '*' | '/' | '%' ) unary-expr } .
// add-expr := mult-expr { ( '+' | '-' ) mult-expr } .
// expr := add-expr .

typedef std::string String;

class Eval {
   public:
   String s;
   int    ix;
   int    sz;
   double n;
   Eval( const String& _s );
   ~Eval( void );
   bool skipws( void );
   bool number( void );
   bool func( void );
   bool base_expr( void );
   bool unary_expr( void );
   bool mult_expr( void );
   bool add_expr( void );
   bool expr( void );
};

Eval::Eval( const String& _s ) : s(_s), ix(0), sz(static_cast<int>(s.size())), n(0.0) { }
Eval::~Eval( void ) { }

bool Eval::skipws( void ) {
   // leerzeichen ueberlesen
   while ( ix < sz && ( s[ix] == ' ' || s[ix] == '\t' || s[ix] == '\n' || s[ix] == '\r' ) ) ++ix;
   return true;
}

bool Eval::number( void ) {
   // number := /[0-9]+\.?[0-9]*[eE]?[+-]?[0-9]*/ ;
   skipws();
   if ( ix < sz && s[ix] >= '0' && s[ix] <= '9' ) {
      const char* t = s.c_str() + ix;
      int cnt = 0;
      if ( sscanf( t, "%lf%n", &n, &cnt ) == 1 ) {
         ix += cnt;
         return true;
      }
   }
   return false;
}

bool Eval::func( void ) {
   // func := 'sqrt' .
   skipws();
   if ( ix < sz && s[ix] >= 'a' && s[ix] <= 'z' ) {
      const char* t = s.c_str() + ix;
      char name[128];
      int cnt = 0;
      int old_ix = ix;
      if ( sscanf( t, "%[a-z]%n", name, &cnt ) == 1 ) {
         ix += cnt;
         do {
            skipws();
            if ( ix < sz && s[ix] == '(' ) {
               ++ix;
               if ( expr() && skipws() && ix < sz && s[ix] == ')' ) {
                  ++ix;
                  if ( strcmp( name, "sqrt" ) == 0 ) {
                     n = sqrt( n );
                     return true;
                  }
                  else {
                     printf( "? invalid function '%s' near '%s'\n", name, t );
                  }
               }
               else {
                  printf( "? ')' expected near '%s'\n", t );
               }
            }
            else {
               printf( "? '(' expected near '%s'\n", t );
            }
         } while ( 0 );
      }
      ix = old_ix; return false;
   }
}

bool Eval::base_expr( void ) {
   // base-expr := number | '(' expr ')' | func '(' expr ')' .
   if ( number() ) return true;
   skipws();
   if ( ix < sz && s[ix] == '(' ) {
      int old_ix = ix;
      ++ix;
      do {
         if ( expr() && skipws() && ix < sz && s[ix] == ')' ) {
            ++ix;
            return true;
         }
         else {
            printf( "? ')' expected near '%s'\n", s.c_str() + ix );
         }
      } while (0);
      ix = old_ix;
      return false;
   }
   return func();
}

bool Eval::unary_expr( void ) {
   // unary-expr := [ '-' ] base-expr .
   skipws();
   if ( ix < sz && s[ix] == '-' ) {
      int old_ix = ix;
      ++ix;
      if ( base_expr() ) { n = -n; return true; }
      ix = old_ix;
      return false;
   }
   else {
      return base_expr();
   }
}

bool Eval::mult_expr( void ) {
   // mult-expr := unary-expr { ( '**' | '*' | '/' | '%' ) unary-expr } .
   if ( !unary_expr() ) return false;
   skipws();
   while ( ix < sz && ( ( s[ix] == '*' && ix+1 < sz && s[ix+1] == '*' ) || s[ix] == '*' || s[ix] == '/' || s[ix] == '%' ) ) {
      int op = 0;
      double n1 = n;
      int old_ix = ix;
      if ( s[ix] == '*' && ix+1 < sz && s[ix+1] == '*' ) { op = 1; ix += 2; }
      else if ( s[ix] == '*' ) { op = 2; ++ix; }
      else if ( s[ix] == '/' ) { op = 3; ++ix; }
      else if ( s[ix] == '%' ) { op = 4; ++ix; }
      if ( op > 0 ) {
         if ( unary_expr() ) {
            switch ( op ) {
               case 1:     n = pow( n1, n );   break;
               case 2:     n = n1 * n; break; 
               case 3:     n = n1 / n; break;
               case 4:     n = fmod( n1, n ); break;
            }
            skipws();
            continue;
         }
         else {
            printf( "? expression expected near '%s'\n", s.c_str() + ix );
         }
      }
      else {
         printf( "? internal error: unknown operator near '%s'\n", s.c_str() + old_ix );
      }
      ix = old_ix;
      return false;
   }
   return true;
}

bool Eval::add_expr( void ) {
   // add-expr := mult-expr { ( '+' | '-' ) mult-expr } .
   if ( !mult_expr() ) return false;
   skipws();
   while ( ix < sz && ( s[ix] == '+' || s[ix] == '-' ) ) {
      int op = 0;
      double n1 = n;
      int old_ix = ix;
      if ( s[ix] == '+' ) { op = 1; ++ix; }

      else if ( s[ix] == '-' ) { op = 2; ++ix; }
      if ( op > 0 ) {
         if ( mult_expr() ) {
            switch ( op ) {
               case 1:  n = n1 + n; break;
               case 2:  n = n1 - n; break;
            }
            skipws();
            continue;
         }
         else {
            printf( "? expression expected near '%s'\n", s.c_str() + ix );
         }
      }
      else {
         printf( "? internal error: unknown operator near '%s'\n", s.c_str() + old_ix );
      }
      ix = old_ix;
      return false;
   }
   return true;
}

bool Eval::expr( void ) { 
   // expr := add-expr .
   return add_expr(); 
}

int main( int argc, char** argv ) {
   for (;;) {
      char buf[1024];
      printf( "formel> " ); fflush(stdout);
      buf[0] = '\0';
      if ( fgets( buf, 1024, stdin ) == 0 ) break;
      if ( buf[0] == '\0' || buf[0] == '\n' ) break;
      String str(buf); int sz = str.size();
      while ( sz != 0 && ( str[sz-1U] == '\n' || str[sz-1U] == '\r' ) ) { str.resize(sz-1U); sz = str.size(); }
      Eval e(str);
      if ( !e.expr() ) {
         printf( "? expression expected: '%s'\n", str.c_str() );
      }
      else {
         printf( "result = %g\n", e.n );
      }
   }
   return 0;
}

Ich hoffe, das hilft Dir weiter!

[hohesC]

Werf ma halt mal einfach ein code hin

Power Off schrieb:

hier erstmal ein Programmtext, den ich neulich fuer jemand anderen mit einem aehnlichen Problem geschrieben habe

wollte der Elefanten fangen?, und innen als aussen definieren.
man sollte schon erklären was der code macht, so finde ich das nicht sehr produktiv, vor allem C++ gehört hier nicht rein(ANSI C)!
da hilft auch kein

Power Off schrieb:

(Ist allerdings C++, sorry)

mfg hohesC

[Power Off]

Falls ich heute noch nach Hause komme, schreib ich euch heut abend mal ein ordentliches Beispiel in ANSI C!

[CarstenJ]

Hi,

SonjaB schrieb:

Ich mache gerade eine Weiterbildung zur Fachinformatikerin und bin in einem sechsmonatigen C Kurs.

nur der C-Kurs dauert 6 Monate oder die gesammte Fortbildung?

[Schmarotzerin!]

Lest dies: http://spotlight.de/zforen/ccc/m/ccc-1108964571-16092.html

Da sucht echt jemand dumme Leute, die dem "armen Mädchen" die Hausaufgaben machen sollen.

Ich werde jetzt mal versuchen, den "dummen Lehrer" ausfindig zu machen und ihn auf diesen und die diversen Spotlight-Treads hinweisen.

Ich finde, es gibt in unserem Land genug BetrügerInnen!

[Hihi]

Hihihi,

die Antwort ist auch gut.

Ich bin echt gespannt wie lange die Leute im anderen Forum brauchen um zu begreifen, dass du nur darauf aus bist kostenlos gedankliche Leistung zu schnorren und auch noch einen Anspruch erhebst, dass man die helfen muss

[Power Off]

SonjaB: Ich habe schonmal angefangen, Dir ein Beispiel-Programm zu schreiben, mit dem Du logische Ausdruecke einlesen, in Syntaxbaeume zerlegen, optimieren und ausdrucken kannst, wird aber moeglicherweise eine Weile dauern.

Ich benutze so was gern um mich aufzuwaermen, oder um zu sehen, ob ich schon muede geworden bin.

Ist mir egal, ob Du eine "faule Studentin" bist, wie manche anderen hier sagen.

Selbst wenn es so waere, kann dieser Thread immer noch dazu dienen, auch von anderen gefunden zu werden, die ein aehnliches oder dasselbe Problem haben.

Solche Sachen gehoeren eigentlich zu den Basics, aber es gibt viel zuwenige Leute, die sich wirklich mit sowas auskennen.

Syntaxbaume sind eigentlich eine ganz einfache Geschichte.

Und schliesslich ist das Forum hier dazu da, Leuten zu helfen, und Denkanstoesse fuer eigene Programme zu geben.

(EDIT: p.s.: Meine E-Mail-Adresse ist: flnca-tyrquil-neyjar@onlinehome.de )

[Power Off]

SonjaB: Also hier ist ein einfaches Programm, das Deine Anforderungen erfuellt:

#include <stddef.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <limits.h>
#include <stdio.h>

/*
*  EBNF fuer Ausdruecke
*  --------------------
*  zahlenwert := /[0-9]+/ .
*  variablenname := /[a-zA-Z_][a-zA-Z0-9_]+/ .
*  basis-ausdruck := zahlenwert | variablenname | '(' ausdruck ')' .
*  unaerer-ausdruck := [ '-' ] basis-ausdruck .
*  multiplikations-ausdruck := unaerer-ausdruck { ( '*' | '/' | '%' ) unaerer-ausdruck } .
*  additions-ausdruck := multiplikations-ausdruck { ( '+' | '-' ) multiplikations-ausdruck } .
*  vergleichs-ausdruck := additions-ausdruck [ ( '==' | '!=' | '>=' | '<=' | '<' | '>' ) additions-ausdruck ] .
*  und-ausdruck := vergleichs-ausdruck { '&&' vergleichs-ausdruck } .
*  oder-ausdruck := und-ausdruck { '||' und-ausdruck } .
*  ausdruck := oder-ausdruck .
*/

/* --- Bool-Typ fuer Aeltere Compiler ---------------------------------------------------------------------- */

#ifndef ISO_C
typedef enum { false, true } bool;
#endif

/* --- Syntaxknoten (Basisstruktur fuer Baumelemente) ------------------------------------------------------ */

typedef enum { 
   SK_BLATT, 
   SK_VERZWEIGUNG 
} Knotentyp;

typedef struct __Syntaxknoten { 
   Knotentyp typ; 
} Syntaxknoten;

/* --- Syntaxblatt (Basisstruktur fuer Baum-Blaetter) ------------------------------------------------------ */

typedef enum { 
   SB_ZAHLENWERT, 
   SB_VARIABLENNAME 
} BlattTyp;

typedef struct __Syntaxblatt { 
   Syntaxknoten knoten; 
   BlattTyp     typ; 
} Syntaxblatt;

/* --- Baum-Blatt-Strukturen ------------------------------------------------------------------------------- */

typedef struct __Zahlenwert { 
   Syntaxblatt blatt; 
   int         wert; 
} Zahlenwert;

typedef struct __Variablenname { 
   Syntaxblatt blatt; 
   char        name[32]; 
} Variablenname;

/* --- Baum-Verzweigungs-Strukturen ------------------------------------------------------------------------ */

typedef enum { 
   OP_UNBEKANNT,
   OP_UMINUS, 
   OP_MAL,
   OP_DURCH,
   OP_REST,
   OP_PLUS,
   OP_MINUS,
   OP_GLEICH,
   OP_UNGLEICH,
   OP_GROESSERGLEICH,
   OP_KLEINERGLEICH,
   OP_GROESSER,
   OP_KLEINER,
   OP_UND,
   OP_ODER
} Operator;

typedef struct __Verzweigung { 
   Syntaxknoten  knoten; 
   Operator      oper;
   Syntaxknoten* zweige[2]; 
} Verzweigung;

/* --- Speicherverwaltung fuer Baum ------------------------------------------------------------------------ */

void* weise_speicher_zu( size_t groesse ) {
   void* block = malloc( groesse );
   if ( block == 0 ) {
      fprintf( stderr, "Nicht genug Speicher, um dem Programm %u Bytes Speicher zuzuweisen.", groesse );
      exit(EXIT_FAILURE);
   }
   return block;
}

Syntaxknoten* erzeuge_zahlenwert( int wert ) {
   Zahlenwert* zw = (Zahlenwert*) weise_speicher_zu( sizeof(Zahlenwert) );
   zw->blatt.knoten.typ = SK_BLATT;
   zw->blatt.typ        = SB_ZAHLENWERT;
   zw->wert             = wert;
   return &zw->blatt.knoten;
}

Syntaxknoten* erzeuge_variablenname( const char* name ) {
   Variablenname* vn = (Variablenname*) weise_speicher_zu( sizeof(Variablenname) );
   vn->blatt.knoten.typ = SK_BLATT;
   vn->blatt.typ        = SB_VARIABLENNAME;
   strncpy( vn->name, name, 31 );
   vn->name[31] = '\0';
   return &vn->blatt.knoten;
}

Syntaxknoten* erzeuge_verzweigung( Operator oper, Syntaxknoten* zweig1, Syntaxknoten* zweig2 ) {
   Verzweigung* vz = (Verzweigung*) weise_speicher_zu( sizeof(Verzweigung) );
   vz->knoten.typ = SK_VERZWEIGUNG;
   vz->oper       = oper;
   vz->zweige[0]  = zweig1;
   vz->zweige[1]  = zweig2;
   return &vz->knoten;
}

void vernichte_syntaxknoten( Syntaxknoten* sk ) {
   switch ( sk->typ ) {
      case SK_BLATT:
         free( sk );
         break;
      case SK_VERZWEIGUNG:
         {
            Verzweigung* vz = (Verzweigung*) sk;
            if ( vz->zweige[0] != 0 ) { vernichte_syntaxknoten( vz->zweige[0] ); vz->zweige[0] = 0; }
            if ( vz->zweige[1] != 0 ) { vernichte_syntaxknoten( vz->zweige[1] ); vz->zweige[1] = 0; }
         }
         free( sk );
         break;
   }
}

/* --- (Teil-)Baum Drucken (als Ausdruck) ------------------------------------------------------------------ */

void drucke_syntaxknoten( Syntaxknoten* sk ) {
   switch ( sk->typ ) {
      case SK_BLATT:
         {
            Syntaxblatt* sb = (Syntaxblatt*) sk;
            switch ( sb->typ ) {
               case SB_ZAHLENWERT:
                  {
                     Zahlenwert* zw = (Zahlenwert*) sb;
                     printf( "%d", zw->wert );
                  }
                  break;
               case SB_VARIABLENNAME:
                  {
                     Variablenname* vn = (Variablenname*) sb;
                     printf( "%s", vn->name );
                  }
                  break;
            }
         }
         break;
      case SK_VERZWEIGUNG:
         {
            Verzweigung* vz = (Verzweigung*) sk;
            const char* s = "???";
            if ( vz->zweige[0] != 0 ) {
               if ( vz->zweige[0]->typ == SK_VERZWEIGUNG ) printf( "( " );
               drucke_syntaxknoten( vz->zweige[0] );
               if ( vz->zweige[0]->typ == SK_VERZWEIGUNG ) printf( " )" );
            }
            switch ( vz->oper ) {
               case OP_UMINUS:         s = "-";    break;
               case OP_MAL:            s = "*";    break;
               case OP_DURCH:          s = "/";    break;
               case OP_REST:           s = "%";    break;
               case OP_PLUS:           s = "+";    break;
               case OP_MINUS:          s = "-";    break;
               case OP_GLEICH:         s = "==";   break;
               case OP_UNGLEICH:       s = "!=";   break;
               case OP_GROESSERGLEICH: s = ">=";   break;
               case OP_KLEINERGLEICH:  s = "<=";   break;
               case OP_GROESSER:       s = ">";    break;
               case OP_KLEINER:        s = "<";    break;
               case OP_UND:            s = "&&";   break;
               case OP_ODER:           s = "||";   break;
            }
            printf( " %s ", s );
            if ( vz->zweige[1] != 0 ) {
               if ( vz->zweige[1]->typ == SK_VERZWEIGUNG ) printf( "( " );
               drucke_syntaxknoten( vz->zweige[1] );
               if ( vz->zweige[1]->typ == SK_VERZWEIGUNG ) printf( " )" );
            }
         }
         break;
   }
}

/* --- Unterprogramme fuer Lexikalische Analyse ------------------------------------------------------------ */

bool ist_zahlenwert_zeichen( int c ) {
   /* zahlenwert := /[0-9]+/ . */
   if ( c >= '0' && c <= '9' ) return true;
   return false;
}

bool ist_erstes_variablennamen_zeichen( int c ) {
   /* variablenname := /[a-zA-Z_][a-zA-Z0-9_]+/ . */
   if ( ( c >= 'a' && c <= 'z' ) || ( c >= 'A' && c <= 'Z' ) ) return true;
   return false;
}

bool ist_variablennamen_zeichen( int c ) {
   /* variablenname := /[a-zA-Z_][a-zA-Z0-9_]+/ . */
   if ( ( c >= 'a' && c <= 'z' ) || ( c >= 'A' && c <= 'Z' ) || ( c >= '0' && c <= '9' ) || c == '_' ) return true;
   return false;
}

/* --- Struktur fuer Lexikalische Analyse ------------------------------------------------------------------ */

typedef struct __Lex {
   int      zeichen;
} Lex;

void initialisiere_lex( Lex* lex ) {
   lex->zeichen = EOF;
}

void lies_zeichen( Lex* lex ) {
   lex->zeichen = getchar();
}

void ueberlese_leerzeichen( Lex* lex ) {
   while ( lex->zeichen == ' ' || lex->zeichen == '\t' ) lies_zeichen( lex );
}

void zeichen_zuruecklegen( Lex* lex, int zeichen ) {
   ungetc( zeichen, stdin );
}

/* --- Syntaktische Analyse -------------------------------------------------------------------------------- */

void fehlerbericht( const char* format, ... ) {
   va_list ap;
   va_start( ap, format );
   vfprintf( stderr, format, ap );
   va_end( ap );
}

Syntaxknoten* lies_zahlenwert( Lex* lex ) {
   /* zahlenwert := /[0-9]+/ . */
   int wert = 0;
   if ( !ist_zahlenwert_zeichen( lex->zeichen ) ) return 0;
   do {
      wert = wert * 10 + ( lex->zeichen - '0' );
      lies_zeichen( lex );
   } while ( ist_zahlenwert_zeichen( lex->zeichen ) );
   return erzeuge_zahlenwert( wert );
}

Syntaxknoten* lies_variablenname( Lex* lex ) {
   /* variablenname := /[a-zA-Z_][a-zA-Z0-9_]+/ . */
   char puffer[32];
   int  ix = 0;
   if ( !ist_erstes_variablennamen_zeichen( lex->zeichen ) ) return 0;
   do {
      if ( ix < 31 ) puffer[ix++] = (char) lex->zeichen;
      lies_zeichen( lex );
   } while ( ist_variablennamen_zeichen( lex->zeichen ) );
   puffer[ix] = '\0';
   return erzeuge_variablenname( puffer );
}

Syntaxknoten* lies_ausdruck( Lex* lex );  /* Vorwaerts-Deklaration (Funktion wird spaeter definiert) */

Syntaxknoten* lies_basis_ausdruck( Lex* lex ) {
   /* basis-ausdruck := zahlenwert | variablenname | '(' ausdruck ')' . */
   Syntaxknoten* sk;
   ueberlese_leerzeichen( lex );
   sk = lies_zahlenwert( lex );    if ( sk ) return sk;
   sk = lies_variablenname( lex ); if ( sk ) return sk;
   if ( lex->zeichen != '(' ) {
      fehlerbericht( "Zeichen '(' erwartet\n" );
      return 0;
   }
   lies_zeichen( lex );
   ueberlese_leerzeichen( lex );
   sk = lies_ausdruck( lex );
   if ( sk == 0 ) {
      fehlerbericht( "Ausdruck erwartet\n" );
      return 0;
   }
   ueberlese_leerzeichen( lex );
   if ( lex->zeichen != ')' ) {
      fehlerbericht( "Warnung: Zeichen ')' erwartet\n" );
      return sk;
   }
   lies_zeichen( lex );
   return sk;
}

Syntaxknoten* lies_unaeren_ausdruck( Lex* lex ) {
   /* unaerer-ausdruck := [ '-' ] basis-ausdruck . */
   ueberlese_leerzeichen( lex );
   if ( lex->zeichen == '-' ) {
      Syntaxknoten* sk;
      lies_zeichen( lex );
      sk = lies_basis_ausdruck ( lex );
      if ( sk == 0 ) {
         fehlerbericht( "Basis-Ausdruck erwartet\n" );
         return 0;
      }
      return erzeuge_verzweigung( OP_UMINUS, sk, 0 );
   }
   return lies_basis_ausdruck( lex );
}

Syntaxknoten* lies_multiplikations_ausdruck( Lex* lex ) {
   /* multiplikations-ausdruck := unaerer-ausdruck { ( '*' | '/' | '%' ) unaerer-ausdruck } . */
   Syntaxknoten* sk_links; 
   Syntaxknoten* sk_rechts;
   Operator      op = OP_UNBEKANNT;
   sk_links = lies_unaeren_ausdruck( lex );
   if ( sk_links == 0 ) return 0;
   ueberlese_leerzeichen( lex );
   switch ( lex->zeichen ) {
      case '*':   op = OP_MAL;   break;
      case '/':   op = OP_DURCH; break;
      case '%':   op = OP_REST;  break;
   }
   if ( op == OP_UNBEKANNT ) return sk_links;   /* kein Multiplikations-Ausdruck, nur unaerer Ausdruck */
   lies_zeichen( lex );
   sk_rechts = lies_multiplikations_ausdruck( lex );     /* da auf rechtem Zweig beliebig viele Multiplikationsausdruecke */
   if ( sk_rechts == 0 ) {
      fehlerbericht( "Multiplikations-Ausdruck erwartet\n" );
      vernichte_syntaxknoten( sk_links );
      return 0;
   }
   return erzeuge_verzweigung( op, sk_links, sk_rechts );
}

Syntaxknoten* lies_additions_ausdruck( Lex* lex ) {
   /* additions-ausdruck := multiplikations-ausdruck { ( '+' | '-' ) multiplikations-ausdruck } . */
   Syntaxknoten* sk_links; 
   Syntaxknoten* sk_rechts;
   Operator      op = OP_UNBEKANNT;
   sk_links = lies_multiplikations_ausdruck( lex );
   if ( sk_links == 0 ) return 0;
   ueberlese_leerzeichen( lex );
   switch ( lex->zeichen ) {
      case '+':   op = OP_PLUS;  break;
      case '-':   op = OP_MINUS; break;
   }
   if ( op == OP_UNBEKANNT ) return sk_links;   /* kein Additions-Ausdruck, nur Multiplikationsausdruck */
   lies_zeichen( lex );
   sk_rechts = lies_additions_ausdruck( lex );     /* da auf rechtem Zweig beliebig viele Additionsausdruecke */
   if ( sk_rechts == 0 ) {
      fehlerbericht( "Additions-Ausdruck erwartet\n" );
      vernichte_syntaxknoten( sk_links );
      return 0;
   }
   return erzeuge_verzweigung( op, sk_links, sk_rechts );
}

Syntaxknoten* lies_vergleichs_ausdruck( Lex* lex ) {
   /* vergleichs-ausdruck := additions-ausdruck [ ( '==' | '!=' | '>=' | '<=' | '<' | '>' ) additions-ausdruck ] . */
   Syntaxknoten* sk_links; 
   Syntaxknoten* sk_rechts;
   Operator      op = OP_UNBEKANNT;
   sk_links = lies_additions_ausdruck( lex );
   if ( sk_links == 0 ) return 0;
   ueberlese_leerzeichen( lex );
   switch ( lex->zeichen ) {
      int z_alt;
      case '!':   z_alt = lex->zeichen;
                  lies_zeichen( lex );
                  if ( lex->zeichen == '=' ) {
                     lies_zeichen( lex );
                     op = OP_UNGLEICH;
                     break;
                  }
                  zeichen_zuruecklegen( lex, z_alt );
                  break;
      case '=':   z_alt = lex->zeichen;
                  lies_zeichen( lex );
                  if ( lex->zeichen == '=' ) {
                     lies_zeichen( lex );
                     op = OP_GLEICH;
                     break;
                  }
                  zeichen_zuruecklegen( lex, z_alt );
                  break;
      case '>':   lies_zeichen( lex );
                  if ( lex->zeichen == '=' ) {
                     lies_zeichen( lex );
                     op = OP_GROESSERGLEICH;
                     break;
                  }
                  op = OP_GROESSER;
                  break;
      case '<':   lies_zeichen( lex );
                  if ( lex->zeichen == '=' ) {
                     lies_zeichen( lex );
                     op = OP_KLEINERGLEICH;
                     break;
                  }
                  op = OP_KLEINER;
                  break;
   }
   if ( op == OP_UNBEKANNT ) return sk_links;   /* kein Vergleichs-Ausdruck, nur Additionsausdruck */
   sk_rechts = lies_additions_ausdruck( lex );     
   if ( sk_rechts == 0 ) {
      fehlerbericht( "Additions-Ausdruck erwartet\n" );
      vernichte_syntaxknoten( sk_links );
      return 0;
   }
   return erzeuge_verzweigung( op, sk_links, sk_rechts );
}

Syntaxknoten* lies_und_ausdruck( Lex* lex ) {
   /* und-ausdruck := vergleichs-ausdruck { '&&' vergleichs-ausdruck } . */
   Syntaxknoten* sk_links; 
   Syntaxknoten* sk_rechts;
   Operator      op = OP_UNBEKANNT;
   sk_links = lies_vergleichs_ausdruck( lex );
   if ( sk_links == 0 ) return 0;
   ueberlese_leerzeichen( lex );
   if ( lex->zeichen == '&' ) {
      int z_alt = lex->zeichen;
      lies_zeichen( lex );
      if ( lex->zeichen == '&' ) {
         lies_zeichen( lex );
         op = OP_UND;
      }
      else zeichen_zuruecklegen( lex, z_alt );
   }
   if ( op == OP_UNBEKANNT ) return sk_links;   /* kein Und-Ausdruck, nur Vergleichausdruck */
   sk_rechts = lies_und_ausdruck( lex );     /* da auf rechtem Zweig beliebig viele Und-Ausdruecke */
   if ( sk_rechts == 0 ) {
      fehlerbericht( "Und-Ausdruck erwartet\n" );
      vernichte_syntaxknoten( sk_links );
      return 0;
   }
   return erzeuge_verzweigung( op, sk_links, sk_rechts );
}

Syntaxknoten* lies_oder_ausdruck( Lex* lex ) {
   /* oder-ausdruck := und-ausdruck { '||' und-ausdruck } . */
   Syntaxknoten* sk_links; 
   Syntaxknoten* sk_rechts;
   Operator      op = OP_UNBEKANNT;
   sk_links = lies_und_ausdruck( lex );
   if ( sk_links == 0 ) return 0;
   ueberlese_leerzeichen( lex );
   if ( lex->zeichen == '|' ) {
      int z_alt = lex->zeichen;
      lies_zeichen( lex );
      if ( lex->zeichen == '|' ) {
         lies_zeichen( lex );
         op = OP_ODER;
      }
      else zeichen_zuruecklegen( lex, z_alt );
   }
   if ( op == OP_UNBEKANNT ) return sk_links;   /* kein Oder-Ausdruck, nur Und-Ausdruck */
   sk_rechts = lies_oder_ausdruck( lex );     /* da auf rechtem Zweig beliebig viele Oder-Ausdruecke */
   if ( sk_rechts == 0 ) {
      fehlerbericht( "Oder-Ausdruck erwartet\n" );
      vernichte_syntaxknoten( sk_links );
      return 0;
   }
   return erzeuge_verzweigung( op, sk_links, sk_rechts );
}

Syntaxknoten* lies_ausdruck( Lex* lex ) {
   /* ausdruck := oder-ausdruck . */
   return lies_oder_ausdruck( lex );
}

/* --- Optimierer ------------------------------------------------------------------------------------------ */

Syntaxknoten* optimiere_syntaxknoten( Syntaxknoten* sk ) {
   Verzweigung* vz; Syntaxknoten* zweig1; Syntaxknoten* zweig2;
   if ( sk->typ != SK_VERZWEIGUNG ) return sk;
   vz = (Verzweigung*) sk;
   /* zuerst Unterknoten optimieren */
   if ( vz->zweige[0] != 0 ) vz->zweige[0] = optimiere_syntaxknoten( vz->zweige[0] );
   if ( vz->zweige[1] != 0 ) vz->zweige[1] = optimiere_syntaxknoten( vz->zweige[1] );
   /* dann diesen Knoten optimieren */
   zweig1 = vz->zweige[0];
   zweig2 = vz->zweige[1];
   switch ( vz->oper ) {
      case OP_UMINUS:
         if ( zweig1 == 0 ) break;
         if ( zweig1->typ == SK_BLATT ) {
            Syntaxblatt* sb = (Syntaxblatt*) zweig1;
            if ( sb->typ == SB_ZAHLENWERT ) {
               /* - x */
               Zahlenwert* zw   = (Zahlenwert*) sb;
               int         wert = zw->wert;
               vernichte_syntaxknoten( sk );
               sk = erzeuge_zahlenwert( - wert );
            }
         }
         break;
      default:
         if ( zweig1 == 0 || zweig2 == 0 ) break;
         if ( zweig1->typ == SK_BLATT && zweig2->typ == SK_BLATT ) {
            Syntaxblatt* sb1 = (Syntaxblatt*) zweig1;
            Syntaxblatt* sb2 = (Syntaxblatt*) zweig2;
            if ( sb1->typ == SB_ZAHLENWERT && sb2->typ == SB_ZAHLENWERT ) {
               Zahlenwert* zw1   = (Zahlenwert*) sb1;
               Zahlenwert* zw2   = (Zahlenwert*) sb2;
               int         wert1 = zw1->wert;
               int         wert2 = zw2->wert;
               int         ergeb = 0;
               switch ( vz->oper ) {
                  case OP_MAL:               ergeb = wert1 * wert2; break;
                  case OP_DURCH:             ergeb = wert1 / ( wert2 != 0 ? wert2 : INT_MAX ); break;
                  case OP_REST:              ergeb = wert1 % ( wert2 != 0 ? wert2 : INT_MAX ); break;
                  case OP_PLUS:              ergeb = wert1 + wert2; break;
                  case OP_MINUS:             ergeb = wert1 - wert2; break;
                  case OP_GLEICH:            ergeb = wert1 == wert2 ? 1 : 0;  break;
                  case OP_UNGLEICH:          ergeb = wert1 != wert2 ? 1 : 0;  break;
                  case OP_GROESSERGLEICH:    ergeb = wert1 >= wert2 ? 1 : 0;  break;
                  case OP_KLEINERGLEICH:     ergeb = wert1 <= wert2 ? 1 : 0;  break;
                  case OP_GROESSER:          ergeb = wert1 >  wert2 ? 1 : 0;  break;
                  case OP_KLEINER:           ergeb = wert1 <  wert2 ? 1 : 0;  break;
                  case OP_UND:               ergeb = wert1 && wert2 ? 1 : 0;  break;
                  case OP_ODER:              ergeb = wert1 || wert2 ? 1 : 0;  break;
               }
               vernichte_syntaxknoten( sk );
               sk = erzeuge_zahlenwert( ergeb );
            }
         }
         break;
   }
   return sk;
}

/* --- Hauptprogramm --------------------------------------------------------------------------------------- */

void lies_bis_zeilenende( Lex* lex ) {
   while ( lex->zeichen != '\n' && lex->zeichen != EOF ) lies_zeichen( lex );
}

int main( int argc, char** argv ) {
   for (;;) {
      Lex lex; Syntaxknoten* sk;
      initialisiere_lex( &lex );
      printf( "Ausdruck> " ); fflush(stdout);
      lies_zeichen( &lex );
      sk = lies_ausdruck( &lex );
      lies_bis_zeilenende( &lex );
      if ( sk == 0 ) { fehlerbericht( "Ausdruck erwartet\n" ); continue; }
      sk = optimiere_syntaxknoten( sk );
      printf( "Ergebnis-Ausdruck: " );
      drucke_syntaxknoten( sk );
      printf( "\n" );
      vernichte_syntaxknoten( sk );
   }
   return 0;
}

Falls Du Fragen dazu hast, kannst Du Dich vertrauensvoll an mich wenden!

[hohesC]

*OMG :p

[@Power Off]

glaubst du das sie dir jetzt einen blaest?