CString in Bool'sche Algebra "umwandeln"

kscha

kscha

Mitglied
Hallo zusammen ;)

Wow, ist das lange her, daß ich mal hier war !
Ich habe folgendes Problem und hoffe, daß mir jemand helfen kann:

Ich habe einen CString in dieser Form: "((0&1&2)|(3&4))&5".
Diese Formel stellt einen Bool'schen Ausdruck dar, wobei die Zahlen Indizes eines BOOL-Arrays sind. Ich würde jetzt gerne diesen Ausdruck auswerten; d.h. es sollte so etwas wie eine Wahrheitstabelle entstehen und die Ergebnisse dieser Formel, die gleich Null sind, werden weiterverarbeitet.

Jetzt meine Frage: Weiß jemand, wie ich aus diesem String eine Rechnung machen kann, um die Ergebnisse zu erhalten ? Das Problem ist nämlich, daß die UNDs und ODERs variabel sind (sie kommen aus einer Eingabe) und deshalb nicht fest codiert sein sollen ! Ich habe keine Ahnung, wie ich das machen könnte :( ....

Ich hoffe, daß ihr mir helfen könnt

Viele Grüße und Danke,

Kai
 
Hallo,

nur nochma zum Verständnis...

0 kann dann true sein, 1 kann dann true sein, 2 kann dann false sein usw. ?
Kann sich natürlich ändern... wollts nur mal anschaulicher vor mir haben ;)

Kannst du mal ein Beispiel posten wie das auszusehn hat?
Dann kann man sich mehr drunter vorstellen...

MfG Turri
 
Hallo,

Vorschlag für einen Algorithmus:
  1. Wenn keine Klammerungen im Ausdruck vorliegen, springe zu 5.
  2. Suche das erste Klammerpaar, das im geklammerten Bereich keine weiteren Klammerungen enthält
  3. Werte den Inhalt des geklammerten Bereichs aus und ersetze ihn samt Klammernpaar im String durch das Ergebnis der Auswertung
  4. Springe zu 1.
  5. Werte den Inhalt des Strings aus und gib das Ergebnis zurück
Schritte 3. und 5. sollte dabei relativ einfach zu implementieren sein. Zuerst den ersten Operanden auslesen und als Zwischenergebnis speichern. Wenn der zu bearbeitende String sonst nichts enthält, ist das Zwischenergebnis gleichzeitig das Endergebnis und man ist fertig. Andernfalls ist jeweils ein Operator-Operand-Paar auszulesen und entsprechend mit dem bisherigen Zwischenergebnis zu verrechnen. Ist man am Ende des zu bearbeitenden Bereichs angelangt, ist wiederum das Zwischenergebnis das Endergebnis.

Bei Schritt 3. könnte man das Ergebnis entsprechend als t oder f kodieren und so in den String schreiben.

Schritt 2. dürfte auch nicht weiter schwer sein. Einfach den String von vorn nach hinten nach einem ( absuchen. Ab dem Fundort dann weiter nach einem ) Ausschau halten. Stößt man dabei auf ein weiteres (, so markiert man den Fundort als neuen Anfang eines möglichen Klammernpaars. Das alles so lange, bis man am Ende angekommen ist (-> fehlerhafte Klammerung) oder tatsächlich ein ) findet (-> Klammerung isoliert).

Viel Erfolg!

Grüße,
Matthias
 
@Turri:

Hui, das ist aber gar nicht so einfach mit dem Beispiel !
Ich glaube, du hast das Problem aber richtig erkannt ! Ich versuche es noch ein bißchen anschaulicher darzustellen.
Wir kennen ja alle aus unserer Schulzeit diese Wahrheitstabellen, die dann u.U. ewig lang werden können. Für dieses Beispiel also ganz kurz (auszugweise):

0 1 2 .....
------------------------
0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
.....

So, wenn man jetzt in die o.g. Formel die Werte einsetzt, dann kommt entweder 1 oder 0 raus. Wenn ich die Formel jetzt fest codieren würde, dann wäre das ja kein Problem. Dann könnte man die ganzen Werte einfach in einer Schleife durchrattern lassen. Aber da sich die logischen Verknüpfungen ja ändern können, bräuchte ich eine Möglichkeit diesen CString in eine Formel umzuwandeln, die man dann "allgemeingültig" auswerten kann.

Ich finde das voll schwierig zu erklären ! Ich hoffe, ich konnte das jetzt einigermaßen verdeutlichen ;)
 
Zuletzt bearbeitet:
Hallo Matthias !

Vielen Dank für deine Antwort !
Aber ich habe da trotzdem noch ein Problem: Angenommen ich nehme den ersten Term des Strings --> "(0&1&2)" und möchte diesen auswerten.
Wie kann ich das aber programmiertechnisch umsetzen ? Der Schritt zwischen String und auswertbarer Rechnung fehlt mir !
Wie gesagt, bei einer festen Codierung, wo die Operatoren immer gleich sind, geht's ja noch. Aber was ist, wenn der Term im nächsten Durchlauf "(0&1|2)" heißt ?
Verstehst du mein Problem ?

Viele Grüße,

Kai
 
Matthias Reitinger hat gesagt.:
ach so, sind die Operatoren auch variabel? Ich dachte, es würden sich höchstens die Operanden ändern.
Zum Vergrößern anklicken....

Ja, leider

Aber ich glaube, ich hatte grad ne Idee ! Vielleicht kannst du mir da zu- bzw. abraten :)
Wenn ich schon gemäß deinem vorgeschlagenen Algorithmus die Klammern zeichenweise checke, dann könnte ich doch auch gleich, sobald ich einen Index (0,1,2,....) erreicht habe, die Stelle bei 'i+1' überprüfen und mit dem Operator halt in eine if-Abfrage (UND oder ODER) gehen..... und die Operanden immer zweierweise verknüpfen !
Meinst du, das macht Sinn

Gruß, Kai
 
Das mit dem zeichenweise durchgehen ist nicht ganz so einfach, da Du ja die Klammern und die Operatorprioritäten beachten mußt.
Ich denke, Du hast 2 Möglichkeiten:
1. Du schreibste eine Funktion 'EvalExpression(string strExp)', die den String parst und sich selbst rekursiv aufruft. Die müßte also bis zum Operator mit der höchsten Priorität suchen, den String dann an dieser Stelle Teilen und sich selber jeweils mit dem linken under dem rechten Teil aufrufen.
2. Du parst den String von links nach rechts und baust einen Baum auf, der den String nachbildet. der würde dann etwa so aussehen wie in der angehängten Grafik.

Die Zahlen mußt Du natürlich durch die Werte in Deinem Array ersetzen.
 

Anhänge

  • 25598attachment.gif
    25598attachment.gif
    1,4 KB · Aufrufe: 38
Zuletzt bearbeitet:
@jokey2:

Ja, das klingt beides sehr sinnvoll !! Nur leider habe ich weder mit dem einen noch mit dem anderen bisher was zu tun gehabt !
Wie würde sowas denn ungefähr in der Praxis aussehen ? Und was wäre "leichter" und überschaubarer (für einen Freizeit-Programmierer) zu implementieren ? ;)

Gruß, Kai
 
Ich denke, Lösung 1 dürfte erstmal einfacher sein. Das geht in etwa folgendermaßen:

Code: 
bool Evaluate(string strExpression)
{
  //1. Alle Klammern entfernen, die den ganzen String umfangen (Vorsicht! Nicht einfach
  // alle Klammern an Anfang und Ende weglöschen. bei z.B. "(1|2) & (3|4)" würdest Du
  // da reinfallen)
  
  //2. den ganzen String Zeichen für Zeichen durchgehen und Dir den Index des
  // niederstrangigen Operators merken.
  
  //3. Den Teilstringvor dem Operator rekursiv auswerten durch Aufruf von Evaluate mit
  // dem linken Teilstring

  //4. Den Teilstring nach dem Operator rekursiv auswerten durch Aufruf von Evaluate mit
  // dem rechten Teilstring

  //5. Die Ergebnisse der Aufrufe 3. und 4. mit dem Operator verknüpfen und
  // Ergebnis zurückgeben

}

Vielleicht hilf Dir das ja schon weiter. Wenn Du' nicht hinkriegst, kannst Du Dich ja wieder melden.

EDIT: Ups da war ein kleiner Denkfehler in Punkt 2. Es muß natürlich der niederstrangige Operator sein.
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück