bool CParser::DoEqu(bool get)
{
        // rekursiv absteigen
        bool left = DoLog(get);

        // gesamte Aussage durchsuchen und auswerten
        for (;;)
                // Aequivalenz gefunden ?
                if (token==_EQU)
                        // ja, rekursiv absteigen und Aussage berechnen
                        left=(DoLog(true)==left);
                else
                        // nein, also fertig
                        return left;
}

// Parser.h: Schnittstelle für die Klasse CParser.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_PARSER_H__C38C8AEC_9836_11D3_BEA0_000021CC8458__INCLUDED_)
#define AFX_PARSER_H__C38C8AEC_9836_11D3_BEA0_000021CC8458__INCLUDED_

#if _MSC_VER >= 1000
#pragma once
#endif // _MSC_VER >= 1000


class CParser
{
public:
        CString PassedFormat;
        // true, wenn ein Fehler aufgetreten ist
        int nMinVars;
        // true fuer die benutzten Variablen an den jeweiligen Stellen
        // ihres ASCII-Codes (stets Kleinbuchstaben !)
        bool Vars[128];
        // enthaelt alle benutzten Variablen als lueckenlose Zeichenkette
        CString ActiveVars;
        // Maximalzahl benutzter Variablen
        enum { MaxVars = 12 };
        // Definition aller zulaessigen Zeichen
        enum Token { _AND='&', _OR='|', _XOR='+', _NOT='!', _EQU='=', _LOG='>',
                                 _LB='(', _RB=')', _TRUE='1', _FALSE='0', _END=0,
                                 _A='a', _B='b', _C='c', _D='d',
                                 _E='e', _F='f', _G='g', _H='h',
                                 _I='i', _J='j', _K='k', _L='l',
                                };
        // Statuscodes nach der Formatierung
        enum ErrorCodes { _OK, _NOTOKEN, _UNKNOWNTOKEN, _NOVARS, _VAREXPECTED,
                              _BRACKETEXPECTED, _BRACKETNOTALLOWED };

        // bereitet Ausdruck auf die Auswertung vor, entfernt Leerzeichen
        int Format(CString &Expression);
        // berechnet Gesamtaussage des Ausdrucks fuer eine spezifische Variablenbelegung
        bool Evaluate();

private:
        // aktuell zu bearbeitendes Zeichen
        Token token;
        // durchlaeuft die Zeichen in der Aussage
        int exprcount;
        // Aussage
        CString expression;

        // ordnet "token" das naechste zu bearbeitende Zeichen zu
        void GetToken();
        // bearbeite Aequivalenzen
        bool DoEqu(bool get);
        // Implikationen
        bool DoLog(bool get);
        // Disjunktionen
        bool DoOr(bool get);
        // Antivalenzen
        bool DoXor(bool get);
        // Konjunktionen
        bool DoAnd(bool get);
        // Elementarbausteine bzw. geklammerte Ausdruecke
        bool DoPrimary(bool get);
};

#endif // !defined(AFX_PARSER_H__C38C8AEC_9836_11D3_BEA0_000021CC8458__INCLUDED_)

////////////////////////////////////////////////////////////////
// Parser.cpp: Implementierung der Klasse CParser, ANSI-C++
//
// Autor:   Stephan Brumme, stbrumme@gmx.de, www.stephan-brumme.de
//
// (C) 1999,2000  Alle Rechte vorhalten
// Die Distribution ist nur zu Demonstrations- und Lehrzwecken in
// unveraenderter Form mit Angabe des Autoren erlaubt.
// Jegliche kommerzielle Verbreitung/Verwendung ist ohne
// Einwilligung des Autoren verboten.
//
// History: Nov-Dez 1999  Erstellung
//          18.12.1999    Dokumentation
//          03.01.2000    deutlich verbesserte Syntaxpruefung
//          14.01.2000    schnellere Auswertung und Code-Verkuerzung
// TODO:    Umwandlung in Postfix-Ausdruck
//
// - stellt einen Parser fuer Boolesche Ausdruecke dar
// - implementiert 12 Variablen (A-L) und die Funktionen
//   Negation, Konjunktion, Antivalenz, Disjunktion, Implikation,
//   Aequivalenz (diese Reihenfolge beginnend mit hoechster Prioritaet)
// - Verschachtelung mit Klammern moeglich
// - rein theoretisch sind auch mehr Variablen moeglich, doch entstehen
//   bei der jetzigen Grenze schon 4096 Moeglichkeiten, das wird langsam
//   zeit- und speicherkritisch fuer Windows (NICHT FUER DIESEN CODE HIER!)
//
// Zusatzinfos: - LieMachineParser.html (auch unter www.stephan-brumme.de)
//              - Sedgewick:   Algorithmen, 2. Auflage
//              - Stroustrup:  Die C++Programmiersprache, 3. Auflage
//              - Wendt:       Vorlesung SST am HPI der Uni Potsdam, 1.FS
//
////////////////////////////////////////////////////////
//
// Referenz-Vorgehensweise:
//
// Format(Aussage)
// Vars[_A],Vars[_B],...,Vars[_L] je nach Benutzung
//    mit booleschen Werten fuellen
// Evaluate()
//
/////////////////////////////////////////////////////////
//
// public-Variablen/Konstanten:
//
//  Anzahl benutzter Variablen
//        int nMinVars;
//
//  true fuer die benutzten Variablen an den jeweiligen Stellen
//  ihres ASCII-Codes (stets Kleinbuchstaben !)
//        bool Vars[128];
//
//  enthaelt alle benutzten Variablen als lueckenlose Zeichenkette
//        CString ActiveVars;
//
//  Maximalzahl benutzter Variablen
//        enum { MaxVars = 12 };
//
//  Definition aller zulaessigen Zeichen
//        enum Token { ... };
////////////////////////////////////////////////////////////
// public-Funktionen:
//  bereitet Ausdruck auf die Auswertung vor, entfernt Leerzeichen
//  Statuscode beachten !
//  int Format(CString &Expression);
//
//  berechnet Gesamtaussage des Ausdrucks fuer eine spezifische Variablenbelegung
//        bool Evaluate();
/////////////////////////////////////////////////////////////////////


// der ganze von VC automatisch generierte Kram

#include "stdafx.h"
#include "Parser.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif


//////////////////////////////////////////////////////////
// public Format:
// bereitet Aussage fuer die Auswertung vor
// wandelt Aussage in Kleinbuchstaben um, entfernt Leerzeichen
// weist ungueltige Zeichen zurueck, kein Grammatik-Check
//
// IN:   &CString - Aussage
// OUT:  int      - Statuscode, bei _OK ist alles i.O.
///////////////////////////////////////////////////////////
int CParser::Format(CString &Expression)
{
        // Variable erwarten
        bool bForceVar = true;
        // Schachtelungstiefe durch Klammerung mitzaehlen
        int nBracketCount = 0;

        // neue Zeichenkette aus Expression aufbauen
        PassedFormat = "";

        // es sollte schon was drinstehen ...
        if (Expression.GetLength()==0)
                return _NOTOKEN;

        // in Kleinbuchstaben umwandeln
        Expression.MakeLower();

        // alle Zeichen durchlaufen
        for (int i=0; i<Expression.GetLength(); i++)
                // Token ueberpruefen
                switch(Expression[i])
                {
                // Leerzeichen ignorieren
                case ' ': continue;

                // zulaessige Token
                // zuerst Variablen / Konstanten
                case _FALSE:; case _TRUE:;
                case _A:; case _B:;        case _C:; case _D:;
                case _E:; case _F:;        case _G:; case _H:;
                case _I:; case _J:;        case _K:; case _L:
                        // es darf jedes Token folgen
                        bForceVar = false;
                        // ok bis hierher
                        PassedFormat+=Expression[i];
                        break;

                // unärer Opator der Negation
                case _NOT:;
                        // Variable muss folgen
                        bForceVar = true;
                        // ok bis hierher
                        PassedFormat+=Expression[i];
                        break;

                // binäre Operatoren
                case _AND:; case _OR:; case _XOR:; case _LOG:; case _EQU:;
                        // Variable erwartet ? wenn ja, dann Fehler
                        if (bForceVar)
                                return _VAREXPECTED;
                        // Variable muss folgen
                        bForceVar = true;
                        // ok bis hierher
                        PassedFormat+=Expression[i];
                        break;

                // oeffnende linke Klammer
                case _LB:;
                        // Verschachtelung mitzaehlen
                        nBracketCount++;
                        // Variable muss folgen
                        bForceVar = true;
                        // ok bis hierher
                        PassedFormat+=Expression[i];
                        break;

                // schliessende rechte Klammer
                case _RB:;
                        // muss erlaubt sein, es darf weder Variable erwartet werden,
                        // noch duerfen mehr rechte als linke Klammern auftauchen
                        if (bForceVar||(nBracketCount==0))
                                return _BRACKETNOTALLOWED;
                        // "zurueckschachteln" (Copyright auf dieses Wort beantragt)
                        nBracketCount--;

                        // ok bis hierher
                        PassedFormat+=Expression[i];
                        break;
                // ungueltiges Token
                default: return _UNKNOWNTOKEN;
                }

        // alle Klammern ordentlich aufgeloest ?
        if (nBracketCount!=0)
                return _BRACKETEXPECTED;

        // es darf keine Variable mehr erwartet werden
        if (bForceVar)
                return _VAREXPECTED;

        // Anzahl Variablen zaehlen
        nMinVars=0;
        // vorkommende Variablen mit ihrem Namen festhalten
        ActiveVars = "";
        // moegliche Namen begrenzen
        CString AllVars = "abcdefghijkl";
        // auf alle moeglichen Variablen ueberpruefen
        for (i=0; i<MaxVars; i++)
                // taucht sie in der Aussage auf ?
        if (PassedFormat.Find(AllVars[i])!=-1)
                {
                        // ja, also vermerken
                        nMinVars++;
                        ActiveVars+=AllVars[i];
                }

        // konstante Ausdruecke sind nicht erlaubt
        if (nMinVars==0)
                return _NOVARS;

        // die formatierte Aussage an Aufrufer zurueckgeben
        Expression = PassedFormat;
        // Formatierung abgeschlossen, fuer die anschliessende Auswertung vormerken
        expression = PassedFormat;
        // Ende fuer die Auswertung markieren
        expression+= _END;

        // fehlerfrei bearbeitet
        return _OK;
}


////////////////////////////////////////////////////////////
// public Evaluate:
//
// wertet Aussage aus, vorher muessen alle verwendeten Variablen
// in "vars" initialisiert werden (Index jeweils der Token _A,_B,...)
//
// IN:  nix
// OUT: bool - false bei Fehlern
////////////////////////////////////////////////////////////////
bool CParser::Evaluate()
{
        // Laufzeiger auf gerade zu bearbeitendes Token
        exprcount = 0;

        // erstes Token holen
        GetToken();

        // Aussage auswerten
        return DoEqu(false);
}


//////////////////////////////////////////////////////////////
// private DoEqu:
//
// alle Aequivalenzen aufloesen
//
// IN:  bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoEqu(bool get)
{
        // rekursiv absteigen
        bool left = DoLog(get);

        // gesamte Aussage durchsuchen und auswerten
        for (;;)
                // Aequivalenz gefunden ?
                if (token==_EQU)
                        // ja, rekursiv absteigen und Aussage berechnen
                        left=(DoLog(true)==left);
                else
                        // nein, also fertig
                        return left;
}


//////////////////////////////////////////////////////////////
// private DoLog:
//
// alle Implikationen aufloesen
//
// IN:  bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoLog(bool get)
{
        // rekursiv absteigen
        bool left = DoOr(get);

        // gesamte Aussage durchsuchen und auswerten
        for (;;)
                // Implikation gefunden ?
                if (token==_LOG)
                        // ja, rekursiv absteigen und Aussage berechnen
                        left=(!left)|DoOr(true);
                else
                        // nein, also fertig
                        return left;
}


//////////////////////////////////////////////////////////////
// private DoOr:
//
// alle Konjunktionen aufloesen
//
// IN:  bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoOr(bool get)
{
        // rekursiv absteigen
        bool left = DoXor(get);

        // gesamte Aussage durchsuchen und auswerten
        for (;;)
                // Disjunktion gefunden ?
                if (token==_OR)
                        // ja, rekursiv absteigen und Aussage berechnen
                        left|=DoXor(true);
                else
                        // nein, also fertig
                        return left;
}


//////////////////////////////////////////////////////////////
// private DoXor:
//
// alle Antivalenzen aufloesen
//
// IN:  bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoXor(bool get)
{
        // rekursiv absteigen
        bool left = DoAnd(get);

        // gesamte Aussage durchsuchen und auswerten
        for (;;)
                // Antivalenz gefunden ?
                if (token==_XOR)
                        // ja, rekursiv absteigen und Aussage berechnen
                        left^=DoAnd(true);
                else
                        // nein, also fertig
                        return left;
}


//////////////////////////////////////////////////////////////
// private DoAnd:
//
// alle Konjunktionen aufloesen
//
// IN:  bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoAnd(bool get)
{
        // rekursiv absteigen
        bool left = DoPrimary(get);

        // gesamte Aussage durchsuchen und auswerten
        for (;;)
        {
                // Konjunktion gefunden ?
                switch (token)
                {
                // ja, explizit markiert, rekursiv absteigen und Aussage berechnen
                case _AND:
                        left&=DoPrimary(true); break;

                // ja, impliziert durch Kurzschreibweise (a&b=ab)
                case _A:; case _B:;        case _C:; case _D:;
                case _E:; case _F:;        case _G:; case _H:;
                case _I:; case _J:;        case _K:; case _L:;
                case _LB:; case _NOT:
                        // rekursiv absteigen und Aussage berechnen
                        left&=DoPrimary(false); break;
                default:
                        // fertich glaubich
                        return left;
                }
        }
}


//////////////////////////////////////////////////////////////
// private DoPrimary:
//
// elementares Token aufloesen bzw. Klammern bearbeiten
//
// IN:  bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoPrimary(bool get)
{
        // ggf. neues Token auslesen
        if (get)
                GetToken();

        // Ergebnis-Zwischenspeicher
        bool temp;

        // Token auswerten
        switch (token)
        {
                // Variableninhalt zurueckgeben
                case _A:; case _B:;        case _C:; case _D:;
                case _E:; case _F:;        case _G:; case _H:;
                case _I:; case _J:;        case _K:; case _L:;
                        temp = Vars[token];
                        // naechtes Token auslesen
                        GetToken();
                        return temp;

                // unaere Negation
                case _NOT:
                        // inverse Aussage des naechsten Tokens zurueckgeben
                        return !DoPrimary(true);

                // Konstante "TRUE"=1
                case _TRUE:
                        // naechtes Token auslesen
                        GetToken();
                        // "TRUE" zurueckgeben
                        return true;

                // Konstante "FALSE"=0
                case _FALSE:
                        // naechtes Token auslesen
                        GetToken();
                        // "FALSE" zurueckgeben
                        return false;

                // oeffnende Klammer
                case _LB:
                        // die Klammer auswerten
                        temp = DoEqu(true);
                        // naechtes Token auslesen
                        GetToken();
                        // Klammerinhalt zurueckgeben
                        return temp;

                // Dummy-Funktion, damit der Compiler nicht meckert
                default: return false;
        }
}


///////////////////////////////////////////////////////////////
// private GetToken
//
// liest ein einzelnes Zeichen aus "expression" aus
//
// IN:  nix, aber indirekt wird "expression" ind "exprcount" benutzt
// OUT: nix, aber "token" wird veraendert
////////////////////////////////////////////////////////////////
void CParser::GetToken()
{
        // Zeichen lesen, Index weiterbewegen
    token = Token(expression[exprcount++]);
}


// That's all folks.