Nicht Standard Form boolesche Funktion in Standard Form parsen

[omen]

Hallo alle zusammen,

ich möchte einen Java Parser schreiben, der eine nicht Standard Form (NSF) boolesche Funktion in eine Standard Form (SF) umwandelt.

Beispiel für eine NSF:

A*B + D(A+B)C + A*B(A*B'+A+B)D

Um eine NSF in eine SF zu bringen, muss man die Klammern ausmultiplizieren. Eine SF von der obigen Funktion sieht also so aus:

A*B + D*A*C + D*B*C + A*B*A*B'*D + A*B*A*D + A*B*B*D

Hat jemand eine Idee, wie ich das am besten umsetzen kann?

danke

 

[Marc T.]

Du könntest eine Grammatik erstellen.
Falls du davon noch nichts gehört hast:

Formale Grammatik ? Wikipedia

Du könntest das ganze so realisieren das du deinen Ausdruck in einem String
speicherst und dann über den String iterierst und die Regeln der Grammatik
abprüfst und das ganze dann verarbeitest und in einen neuen String speicherst.

 

[omen]

Danke erstmal für deine Antwort.

Ich habe ein paar pdfs über formale Grammatik gedownlaodet und gelesen, trotzdem weiß ich noch nicht, wie ich eine Regel erstelle, die alles ausserhalb der Klammern, mit allen dadrine Terme multiplitziert.

 

[Marc T.]

Ich würde das denke ich in etwas so machen:

A*(B + C)

Nach Klammer suchen und dann das erste Element aus der Klammer überprüfen
in diesem Fall ist das erste Element ein B, das würde ich dann rausnehmen:

A*B( + C)

Wieder das nächste element innerhalb der Klammer suchen, jetzt ist es das Plus,
das würde ich dann so behandeln:

A*B( C) +

Der nächste Schritt währe dann das A hinter dem Plus anzuschreiben (das hättest
du also vor dem aller ersten Schritt irgendwo zwischenspeichern müssen in ner Variable)

A*B( C) + A*

Dann wieder das Zeichen in der Klammer:

A*B() + A*C

Und dann nur noch die Klammern löschen:

A*B + A*C

Du musst also grob immer testen wie viele Elemente du in der Klammer hast und wie
viele Operatoren und für jedes Element und für jeden Operator immer diese Aktionen
ausführen.

Du solltest dir am besten zuerst mit Stift und Papier überlegen, welche Fälle du
alle abdecken musst und für dafür einfach deine if-Abfragen aus.