AND-OR Bedingungen umschreiben

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Hi!
Ich dachte mir mal so, dass ja bei Datenbankenanfragen es ja sehr verschraenkte and-or-Bedinungen gibt, am besten dann noch mit Klammern. Da behaelt man selbst schwer den Ueberblick, und als ich das mit Python umsetzen wollte, sass ich da erst mal vor einer Wand. Mein Ziel war naemlich, dass in eine Liste von and-Bedingungen umzuschreiben.

Also Beispiel:

Code: Alles auswählen

IF A = 13 OR B = 'house'
Dies kann man sich als Bruchstueck aus zum Beispiel SQL vorstellen.
Das sollte dann gerne zu dem hier oder etwas aehnlich Uebersichtlichem werden:

Code: Alles auswählen

(((A, (13,))), ((B, ('house',))))
Den zweiten Wert im Tuple hab ich wieder in einen Tuple getan, damit es auch moeglich ist, mehrere Bedingungen zu stellen, also ueber eine AND-Verknuepfung. Das erste waer dann der Tuple zum Buendeln der OR-Verknuepfungen, der zweite zum Buendeln der AND-Verknuepfung und der Dritte schliesst dann den Spaltennamen mit dem/den Wert(en) zusammen. Das ist jetzt von mir frei erfunden, falls es bessere Ideen gibt, sofort posten!

Das ganze soll aber nicht nur das hier, sondern auch viel kompliziertere Sachen loesen, wie auch zum Beispiel:

Code: Alles auswählen

IF (A = 45 OR C = 23) AND (B = 48 OR D = 59)
Das wuerde ja zu dem hier werden:

Code: Alles auswählen

(
((A, (45,)), (B, (48,)), 
((A, (45,)), (D, (59,)),
((C, (23,)), (B, (48,))
((C, (23,)), (D, (59,))
)
Gibt es sowas schon in Python? Muesste es ja eigentlich, oder? Wo koente ich denn da mal in einem guten OpenSource-Projekt nachkucken?
Gibt es dafuer bereits gute Module, mit denen das leicht umsetzbar ist? Muesste ich das wirklich mit RE auseinanderbasteln oder kann ich das implementierte aus Python benutzen? Also in Python selbst gibt es ja auch schon diese umstaendlichen AND-OR-Bedingungen.
Mein Ding ist halt, dass ich zwar den and-or-Kram auch ueber exec ausfuehren koennte, ich aber der Quelle nicht vertrauen kann, daher das ziemlich gefaehrlich ist.

Schon mal vielen Dank fuer die Antworten! Falls es noch irgendwelche Fragen gibt, stellt sie!
http://www.cs.unm.edu/~dlchao/flake/doom/
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Ich finde dein System recht unpraktisch, vorallem ist es sehr beschränkt. Drückt man das Problem in KNF aus, wird es etwas übersichtlicher:

Code: Alles auswählen

p = ((A==45, C==23), (B==48, D==59))
print all(map(any, p))
Übersichtlicher als ein if-Statement sind aber beide Varianten nicht unbedingt.
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Ich fand das System um einiges praktischer fuer die Programmierung als das andere, was wir zwar lesen koennen, ich aber nicht weiss, wie ich das dem PC beibringen soll. Da ist das mit den ganzen AND-Bedinungen, die durch OR-Bedingungen verbunden sind, praktischer. Es ist mehr Text, ja, aber dafuer muss wenger gerechnet werden. Man macht ja praktisch aus

Code: Alles auswählen

IF(A = 45 OR B = 94) AND C = 39
Dann:

Code: Alles auswählen

IF A =45 AND C = 39 OR B=94 AND C=39
Das empfinde ich als maschinenfreundlicher, oder hast du da einen anderen Weg, das so zu machen? Weil ja auch noch immer die Klammern beruecksichtigt werden muessen. Da musst du ja auch noch drauf achten.

Um das noch weiter auszufuehren: Die Variablen kenne ich noch nicht, sie liegen mir als Text vor, Entschuldigung, das hab ich unten im Code nicht sauber geschrieben. Also die Variablen liegen mir als Text(String) vor, ich muss sie spaeter noch heraussuchen, muss aber schon wissen, mit was das verglichen werden soll.

Ziel ist es, die AND/OR-Bedinungen in eine feste Struktur zu bringen, die einfach mit einer Schleife abgearbeitet werden kann. Ich habe waehrenddessen keinen Zugriff auf die Variablen, mache aus purem Text aber schon Listen/Tuples odedr sonstige Standarddatentypen aus Python.
Meine Liste oben sieht zwar kompliziert aus, kann aber leicht mit der Schleife durchgeschaut und dann die Variablen nachgeschauen werden.
http://www.cs.unm.edu/~dlchao/flake/doom/
BlackJack

Kannst Du vielleicht nochmal verraten welches Problem Du eigentlich lösen willst?

Was sollen Nutzer eingeben? Die Tupel? Das ist eklig. Oder beliebige durch 'AND' und 'OR' verknüpfte Vergleiche? Das ist für Menschen in der Regel leichter zu verstehen.

Was die Geschwindigkeit angeht: Beim umschreiben in eine Normalform können eventuell mehr Tests entstehen, also muss auch mehr abgearbeitet werden. Ausserdem kann der ursprüngliche Ausdruck ja schon so geschrieben sein, das wichtige Entscheidungen zuerst getroffen werden, so das Unterausdrücke wesentlich weniger oft überhaupt noch ausgewertet werden müssen.

Falls Deine Eingabe wirklich so eine Bedingung wie '(A = 45 OR B = 94) AND C = 39' als Text ist, würde ich einen Parser schreiben, der den Ausdruck in einen Syntaxbaum überführt und den dann abarbeiten. Nettes Modul für so etwas ist PyParsing.
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Also das Problem ist, dass ich einen String bekomme mit einer beliebigen Struktur aus AND/OR und Klammern. Diesen will ich moeglichst unkompliziert auswerten. Dabei dachte ich, dass es am einfachsten ist, wenn ich den in einen Baum bringe und von dort aus weiterverwende, weil ja parsen und sofort machen ja etwas umschoen aussieht.
Wie man da raushoeren kann, hab ich davon nicht ganz so viel Ahnung, haette sie aber schon gerne. Hab mir auch schon mal RE angesehen, aber wie man damit solche Probleme loest, weiss ich nicht. Ich schau mir da mal PyParsing an.

EDIT: Sieht ganz gut schon mal aus, vielen Dank!
http://www.cs.unm.edu/~dlchao/flake/doom/
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Nein, mit Regulären Ausdrücken brauchst du da gar nicht kommen. Sobald es um beliebig verschachtelte Strukturen geht, kannst du die vergessen.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Um allgemein Sätze einer Sprache zu lesen und zu verstehen, brauchst du eine Grammatik, die den Sprachumfang definiert und alle gültigen Sätze beschreibt und dann ein Programm, was dann Sätze anhand dieser Grammatik interpretiert.

(E)BNF ist ein Grammatik, mit der man Grammatiken beschreiben kann.

Ein Programm, das Sätze in eine Computerrepräsentation verwandelt, nennt man Parser. Ein Programm, dass die Computerprepräsentation dann interpretiert, meist Interpreter. Wird die Computerrepräsentation in etwas anderes umgewandelt, spricht man von einem Übersetzer oder auch Compiler.

Eine mögliche Grammatik für das Beispiel könnte sein:

Code: Alles auswählen

rule = "IF" or-expr.
or-expr = and-expr {"OR" and-expr}.
and-expr = p-expr {"AND" p-expr}.
p-expr = eq-expr  | "(" or-expr ")".
eq-expr = var "=" lit.
var = "A" | "B" | ... "Z".
lit = num | str.
num = digit {digit}.
digit = "0" | "1" | ... "9".
str = "'" {any-char-but-quote-or-backslash | "\\" | "\'"} "'".
Die Grammatik ist einfach genug, um dafür per Hand einen Parser zu bauen. Alternativ könntest du dir PyParsing oder einen andere Parsing-Expression-Grammar-Bibliothek anschauen (z.B. hier).
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Da kann ich ja noch mal weiterkucken...
Oder faellt vielleicht einem von euch ein Projekt ein, wo sowas bereits mal geschrieben worden ist? Da bin ich doch bestimmt nicht der erste, der sowas braucht, oder?
http://www.cs.unm.edu/~dlchao/flake/doom/
BlackJack

Bei PyParsing gibt's zwei Beispiele, die für Dich vielleicht interessant sein könnten: searchparser.py und simpleBool.py
Antworten