CString in Bool'sche Algebra "umwandeln"

[Matthias Reitinger]

Hallo,

Das mit dem zeichenweise durchgehen ist nicht ganz so einfach, da Du ja die Klammern und die Operatorprioritäten beachten mußt.

Die Klammern werden mit meinem Algorithmus ja korrekt ausgewertet. Bei der Rangfolge der Operatoren bin ich davon ausgegangen, dass alle Operatoren die gleiche Priorität besitzen (also von links nach rechts abgearbeitet werden).

Die Variante mit dem binären Baum wäre natürlich die schönste, aber wohl auch am aufwändigsten.

Grüße,
Matthias

 

[kscha]

@jokey2 & Matthias:

Hallo !
Erstnal vielen vielen Dank euch beiden für eure Hilfe ! Ich bin einfach immer wieder begeistert über die Hilfsbereitschaft in diesem Forum !

Also ich werde das dann mal probieren mit dem rekursiven Aufruf einer Funktion.... und gegebenenfalls werde ich mich dann nochmal melden (ganz bestimmt sogar ).

Jetzt bleibt erstmal nur noch eine Frage: Was ist der niederstrangige Operator und wie erkenne ich den ?

Gruß, Kai

 

[jokey2]

Was ist der niederstrangige Operator und wie erkenne ich den ?

Nun, das läßt sich leider nicht erkennen, das muß man wissen.
Aus dem Matheunterricht weißt Du wahrscheinlich noch, daß Multiplikation und Division vorrangig sind vor Addition und Subtraktion (kurz: Punkt vor Strich). Diesen Vorranh gibt es auch bei booleschen Operatoren. So hat z.B. das logische UND Vorrang vor dem logischen ODER.
Eine Tabelle mit den C++-Operatoren findest Du z.B. hier. Oben sind die höchstrangigen, nach unten abnehmend.
Was mathematische Operatoren angeht, so orientiert sich die Tabelle daran. Du kannst die Reihenfolge also so übernehmen. Beachte, daß das logische UND in C/C++ '&&' geschrieben wird und das logische ODER '||'.

 

[kscha]

Hallo

Jetzt habe ich mal wieder Zeit mich ausgiebiger mit diesem Problem zu beschäftigen..... aber irgendwie komme ich nicht damit zurecht, einen geeigneten Algorithmus zu finden ! Mein Problem ist es, eine wirklich allgemeingültige Verarbeitung zu "bauen"; so daß es völlig egal ist, wie die Formel lautet.

Wenn ich jetzt beispielsweise in der Formel von oben "((0&1&2)|(3&4))&5" den String beim ODER in zwei Teilstrings aufspalte, dann kann ich mir das ja noch vorstellen. Aber wenn ich jokey's Beispiel nehme "(1|2) & (3|4)", dann habe ich beim Suchen und Aufspalten beim ODER ein Problem.

Ich komme mir echt blöd vor, weil ich da nicht weiterkomme ! Könnt ihr mir vielleicht nochmal unter die Arme greifen

Viele Grüße,
Kai

 

[jokey2]

Vielleicht hilft es Dir weiter, wenn ich zum Punkt 2 meiner Auflistung oben noch hinzufüge, daß Klammern den Vorrang eines Operators natürlich erhöhen. In dem genannten Beispiel ist der niederstrangige Operator dann der &-Operator, da er nicht in einer Klammer ist. Der Punkt 2 meiner Auflistung erweitert sich so implizit zu:

//2. den ganzen String Zeichen für Zeichen durchgehen und Dir den Index des
// niederstrangigen Operators merken, der nicht innerhalb von Klammern steht.

Wenn Du also beim Parsen des Strings auf eine öffnende Klammer stößt, dann inkrementierst Du einen Klammerzähler. Bei einer schließenden Klammer dekrementierst Du den Zähler wieder. Dann schaust Du nur nach dem Vorrang von Operatoren, wenn der Klammerzähler 0 ist. Deshalb mußt Du am Anfang des Algorithmus alle Klammern entfernen, die den ganzen Ausdruck umschließen.

Noch ein kleiner Hinweis: Ein weiterer Stolperstein ist der Negationsoperator '!', da er nur einen Operanden auf der rechten Seite hat.

 

[kscha]

Ok, vielen Dank ! So langsam kann ich's mir vorstellen ! In meinem Geiste kommt so langsam Licht in die Sache

Jetzt noch eine Frage: Ich hab jetzt verstanden, warum die äußerste umschliessende Klammer weg muss. Wenn ich jetzt aber auf solche "(1|2)&(3|4)" Sachen aufpassen muss, wie erkenne ich dann die komplett umschliessende Klammer (falls eine da ist), wenn ich nicht einfach die erste und die letzte wegnehmen kann ?

Gruß, Kai

 

[jokey2]

Du gehst den String zeichenweise von vorne bis hinten durch und inkrementierst bzw. dekrementierst den Klammerzähler.
Wenn der Klammerzähler innerhalb des Strings 0 wird, ist keine umschließende Klammer da und Du kannst abbrechen.
Wenn der Klammerzähler erst am Ende des Strings 0 wird (und das erste Zeichen im String eine öffnende Klammer ist), hast Du umschließende Klammern und entfernst sie.
Sollte der Klammerzähler gar nicht auf 0 gehen, hast Du eine öffnende Klammer zuviel ;-)

 

[kscha]

Hallo.... ich bin's schon wieder

Ich versuche es relativ kurz zu machen, was mir jetzt wieder auf dem Herzen liegt (und vor allem verständlich, was noch viel schwieriger ist):
Wenn ich jetzt diesen Term habe "((0&1&2) | (3&4)) & (5 | 6)", dann zerpflückt meine Funktion diesen in

links = ((0&1&2) | (3&4)) und
rechts = (5 | 6)

Das ist ja auch gut so. Mit dem linken Teil gehe ich wieder in die Funktion, entferne die äußere Klammer und weiter geht's...... --> (0&1&2) und (3&4)
Jetzt meine Frage: Wie merke ich mir die ganzen Teilterme, um sie zum Schluss für die Auswertung dann wieder richtig zusammen bauen zu können ? Ich kann ja erst auswerten, wenn keine Klammern mehr in den Teiltermen sind (Solange wird ja rekursiv aufgerufen) ?! Und ich muss ja auch irgendwie den Unterschied zwischen "kommt von links" und "kommt von rechts" machen. Soll ich die in einem Array zwischenspeichern ?

Ich hoffe, das war verständlich ?!

Gruß, Kai

 

[jokey2]

Das ist doch gerade der Trick beim rekursiven Aufruf. Du brauchst nichts zwischenzuspeichern, das macht der Stack für Dich. Jeder Aufruf von Evaluate gibt Dir das Ergebnis des übergebenen Ausdrucks. Du rufst also Evaluate jeweils für den linken und den rechten Teilausdruck auf, verknüpfst die Ergebnisse mit dem gefundenen Operator und gibst das Ergebnis zurück.
Wenn in einem Ausdruck kein Operator gefunden wurde, hast du einen Operanden und gibst dessen Wert zurück.
Etwa so:

bool Evaluate(string strExpression)
{
    string strLeftExpression, strRightExpression;
    char cOperator = 0;
    
    // bis hier hast Du den Ausdruck in linken Teil, rechten Teil und Operator zerlegt

    // Auswerten
    if(cOperator == '&')
    {
        return Evaluate(strLeftExpression) && Evaluate(strRightExpression);
    }
    else if(cOperator == '|')
    {
        return Evaluate(strLeftExpression) || Evaluate(strRightExpression);
    }
    else
    {
        return WertVon(strExpression);
    }
}

 

[kscha]

Cool.... vielen Dank !!

Da ich noch nie mit rekursiven Funktionsaufrufen gearbeitet habe, wußte ich bisher nur, daß das eine Funktion ist, die sich selbst aufruft.

Na, ok. Die Funktion läuft so weit, daß die Formel zerpflückt wird, bis nur noch "0&1" übrig bleibt.

linkerTeil = 0
rechterTeil = 1
cOperator = '&'

Jetzt fehlt mir eigentlich nur noch der "Brückenschlag" zur eigentlichen Auswerte-Funktion (in deinem Beispiel 'return WertVon(strExpression);' ).

Ich will ja ALLE möglichen logischen Verknüpfungen durchgehen (wie in einer Wahrheitstabelle) und alle Kombinationen, bei denen die Formel 0 ergibt, schreibe ich in eine Datei. Wie muss die Auswertungsfunktion aufgebaut sein bzw. wie kann ich es bewerkstelligen, daß ich nicht nur ein Ergebnis kriege, sondern alle ? Mit meinem 'return' gebe ich ja nur einen Wert zurück.
Irgendwo muss ich doch dann einen Funktionsaufruf in einer Schleife öfter durchlaufen lassen ?! Wo mache ich das am Besten ?

Gruß, Kai