Hallo,
ich bin gerade daran einen Parser für meine Python-Reimplementation von TIGERSearch zu schreiben. Dazu muss ich boolsche Anfragen parsen und normalisieren. Dazu muss ich Listen "ausmultiplizieren". Z.B;
A & B | C
Ergibt: [[A, B], [A,C]]
oder
( A | B | C ) & D & ( E | F )
Ergibt:
[
[A, D, E],
[A, D, F],
[B, D, E],
[B, D, F],
[C. D. E],
[C, D, F]]
Kann mir jemand einen Tipp geben (keinen Code!), wie ich das Problem am besten angehe? Gibt es da möglicherweise etwas in den Batterien, das ich übersehen habe? Meine bisherigen Implementationen lassen etwas zu wünschen übrig, und ich habe mich gefragt, ob es möglicherweise eine bessere Methode gibt.
Vielen Dank für die Tipps
Ausmultiplizieren von Listen
Hm, insbesondere wenn ich Dein zweites Beispiel anschaue, dann hätte ich eher [[A, B], [C]] erwartet. `&` bindet stärker als `|`. Aber Du hast sicher nur die Klammern vergessen.Clython hat geschrieben:A & B | C
Ergibt: [[A, B], [A,C]]
Ohne zu wissen was Du implementiert hast, lässt sich schlecht sagen ob ein Vorschlag besser ist.oder
( A | B | C ) & D & ( E | F )
Ergibt:
[
[A, D, E],
[A, D, F],
[B, D, E],
[B, D, F],
[C. D. E],
[C, D, F]]
Kann mir jemand einen Tipp geben (keinen Code!), wie ich das Problem am besten angehe? Gibt es da möglicherweise etwas in den Batterien, das ich übersehen habe? Meine bisherigen Implementationen lassen etwas zu wünschen übrig, und ich habe mich gefragt, ob es möglicherweise eine bessere Methode gibt.
Hast Du die Ausdrücke immer in dieser Form? Also so das man sie als Liste darstellen kann in der die "oder"-Elemente ihrerseits in Listen zusammengefasst sind? Dein zweites Beispiel wäre also als Eingabe für eine Funktion [[A, B, C], [D], [E, F]].
Dann gibt's zwei Wege. Eine einfache rekursive Lösung, oder Du bastelst Dir eine Art "Zählwerk". Dazu brauchst Du einen Zähler/Index pro Unterliste die alle bei 0 anfangen. Wenn der erste noch kleiner ist als die Länge seiner Liste, dann zählst Du ihn einen rauf. Ansonsten setzt Du ihn wieder auf 0 und zählst den nächsthöheren Zähler/Index nach dem gleichen Muster hoch. Für das zweite Beispiel ergeben sich also die folgenden Zählerstände:
[0, 0, 0]
[1, 0, 0]
[2, 0, 0]
[0, 0, 1]
[1, 0, 1]
[2, 0, 1]
Wenn man den letzten Zähler auch nochmal um eins raufzählen wollte, dann würde es einen "Übertrag" geben. Das ist das Zeichen aufzuhören.
Willst Du alle Möglichkeiten aufzählen um die dann gegen etwas zu testen? Das ginge bei "und"- und "oder"-Verknüpfungen sicher effizienter wenn Du die Stück für Stück auswertest, anstatt alle Kombinationen aufzuzählen. Vor allem weil man vorzeitig aufhören kann, wenn das Ergebnis sich nicht mehr ändern kann.
Ich würde vermutlich so herangehen, dass ich erstmal den zu multiplizierenden Ausdruck korrekt in eine Struktur bekomme, also, dass
a & b | c
in etwa durch irgendwelche Baumartigen Objekte repräsentiert wird, bei denen (wenn ich deine Präzedenzen richtig verstanden habe) das oberste objekt ein "und" ist, welches als kinder das atom a, und ein "oder" mit den kindern b und c hat.
Dann könnte man den Objekten beibringen, dass sie ihre Wahrheitslisten, indem sie die ihrer kinder verschmelzen.
a & b | c
in etwa durch irgendwelche Baumartigen Objekte repräsentiert wird, bei denen (wenn ich deine Präzedenzen richtig verstanden habe) das oberste objekt ein "und" ist, welches als kinder das atom a, und ein "oder" mit den kindern b und c hat.
Dann könnte man den Objekten beibringen, dass sie ihre Wahrheitslisten, indem sie die ihrer kinder verschmelzen.
Nein, ich habe die Klammer nicht vergessen, ich hätte es nur so schreiben sollen:BlackJack hat geschrieben:Hm, insbesondere wenn ich Dein zweites Beispiel anschaue, dann hätte ich eher [[A, B], [C]] erwartet. `&` bindet stärker als `|`. Aber Du hast sicher nur die Klammern vergessen.Clython hat geschrieben:A & B | C
Ergibt: [[A, B], [A,C]]
[[A & D & E] | [A & D & F] | ...]
Hilft das jetzt weiter? Gibt es vielleicht irgendwo eine implementation eines boolschen Parsers?
Ja gibt es: python kann boolsche ausdrücke auswerten, wenn du | durch or und & durch and ersetztClython hat geschrieben:Hilft das jetzt weiter? Gibt es vielleicht irgendwo eine implementation eines boolschen Parsers?
ne, ernsthaft, solange du nur buchstaben, klammern und &/| hast, ist so ein Parser nicht all zu schwer zu basteln. Es gibt auch Bibliotheken, die einem den Parserbau vereinfachen (PyParse oder so).
Ich meinte bei ``A & B | C`` hast Du die Klammern vergessen. Das müsste `` A & (B | C)`` heissen um zu Deinem Ergebnis zu passen.Clython hat geschrieben:Nein, ich habe die Klammer nicht vergessen, ich hätte es nur so schreiben sollen:BlackJack hat geschrieben:Hm, insbesondere wenn ich Dein zweites Beispiel anschaue, dann hätte ich eher [[A, B], [C]] erwartet. `&` bindet stärker als `|`. Aber Du hast sicher nur die Klammern vergessen.Clython hat geschrieben:A & B | C
Ergibt: [[A, B], [A,C]]
[[A & D & E] | [A & D & F] | ...]
Zum Parsen: Ich habe mit `PyParsing` ganz gute Erfahrungen gemacht.
Hallo,
ich habe zur Zeit das gleiche Problem zu loesen. Allerdings moechte ich das ganze in Ruby implementieren. Daher bin ich eher allgemein an der Beschreibung eines Algorithmus interessiert. Ich weiss, dass das hier nicht das richtige Forum ist, aber dieser Thread war die einzige Quelle im Netz, die ich dazu gefunden habe. Kann mir vielleicht jemand weiterhelfen? Auch Links wuerden weiterhelfen.
Vielen Dank!
ich habe zur Zeit das gleiche Problem zu loesen. Allerdings moechte ich das ganze in Ruby implementieren. Daher bin ich eher allgemein an der Beschreibung eines Algorithmus interessiert. Ich weiss, dass das hier nicht das richtige Forum ist, aber dieser Thread war die einzige Quelle im Netz, die ich dazu gefunden habe. Kann mir vielleicht jemand weiterhelfen? Auch Links wuerden weiterhelfen.
Vielen Dank!
Es wurde ja schon einiges hier gesagt. Kannst Du das Problem dass Du hast etwas präzisieren? Wie sieht die Eingabe aus? Hängts am Parsen oder am "ausmultiplizieren"?