Python: Logische Zeichenfolge in Liste von Listen einteilen

Question

Ich bekomme eine Reihe von logischen Ausdrücken aus einer Datenbank und muss diese in eine Liste von Listen zur weiteren Auswertung einfügen. Ich habe schon viel über das String-Parsing gelesen, konnte aber die Antwort bisher nicht finden. Zum besseren Verständnis des Problems, sind hier drei Beispiele:

input_string1 = '((A OR B) AND (C OR D)) OR E' 
input_string2 = '(A AND (B OR C) AND D AND E)' 
input_string3 = ' A OR (B AND C) OR D OR E' 

erwartet ouput:

Results_string1=[ ['A', 'C'], ['A','D'], ['B','C'], ['B','D'], ['E']] 
Results_string2=[ ['A', 'B', 'D', 'E'], ['A', 'C', 'D', 'E'] ] 
Results_string3=[ ['A'], ['B','C'], ['D'], ['E'] ] 

Also im Grunde muss ich die voll faktorisierter Ausdrücke in Bezug auf OR und diese in die Liste gesetzt. Dies bedeutet, dass jede Bedingung ausgedrückt wird, indem beide Ausdrücke in derselben sublist vorliegen, während jede OR Bedingung die Erstellung neuer Unterlisten auslöst.

e.g. E AND F --> [E, F], E OR F --> [[E],[F]] 

Die Strings aus der Datenbank haben eine beliebige Länge und eine beliebige Anzahl von Klammern.

Jeder hat eine Idee, wie die Grammatik zu definieren, so dass ich z. das Pyjarsing-Paket?

Der Beginn der Grammatik so weit ist:

import pyparsing as pp 
gene_id = pp.Word(pp.alphanums) 
logical = (pp.Keyword("AND") | pp.Keyword("OR")).setName("logical") 
l_brackets = (pp.Literal('(')).setName('l_brackets') 
r_brackets = (pp.Literal(')')).setName('r_brackets') 

Aber wie habe ich den echten Parser definieren?

Eines der Hauptprobleme ist, dass ich nicht weiß, wie man mit den willkürlich auftretenden Klammern und variierenden Länge der Zeichenfolge umgehen soll. Ich habe mit der nestedExpr()-parser aus der Toolbox pyparser herum gespielt, aber konnte das korrekte Verhalten bis jetzt nicht herstellen.

Answer 1

Hier ist eine Lösung, die das gewünschte Ergebnis mit einem Tokenizer und einem rekursiven Descent-Parser liefert. Leider kenne ich die pyparsing Bibliothek nicht, also habe ich sie nicht benutzt.

s1 = '((A OR B) AND (C OR D)) OR E' 
s2 = '(A AND (B OR C) AND D AND E)' 
s3 = ' A OR (B AND C) OR D OR E' 

class Token: 
    def __init__(self, name, value, location): 
     self.name = name 
     self.value = value 
     self.location = location 

    def __repr__(self): 
     return self.name 

def tokenize(s): 
    index = 0 
    tokens = [] 
    while index < len(s): 
     c = s[index] 

     if c == '(': 
      tokens.append(Token('LPAREN', '(', index)) 
      index += 1 
      continue 
     elif c == ')': 
      tokens.append(Token('RPAREN', ')', index)) 
      index += 1 
      continue 
     elif s[index:index+2] == 'OR': 
      tokens.append(Token('OR', 'OR', index)) 
      index += 2 
      continue 
     elif s[index:index+3] == 'AND': 
      tokens.append(Token('AND', 'AND', index)) 
      index += 3 
      continue 
     else: 
      start = index 
      while index < len(s) and s[index].isalpha(): 
       index += 1 
      if not start == index: 
       tokens.append(Token('SYMBOL', s[start:index], start)) 
      else: 
       index += 1 

    return tokens 

def eval_and(left, right): 
    result = [] 
    for l in left: 
     for r in right: 
      result.append(l+r) 

    return result 

def eval_or(left, right): 
    left.extend(right) 
    return left 

def parse_symbol(tokens, index): 
    token = tokens[index] 
    if token.name == 'SYMBOL': 
     return ([[token.value]], index+1) 
    else: 
     raise 

def parse_paren(tokens, index): 
    lparen = tokens[index] 
    index += 1 
    if not lparen.name == 'LPAREN': 
     raise 

    result, index = parse_expr(tokens, index) 

    rparen = tokens[index] 
    index += 1 
    if not rparen.name == 'RPAREN': 
     raise 

    return (result, index) 

def parse_expr(tokens, index): 
    left = None 
    right = None 

    token = tokens[index] 
    if token.name == 'LPAREN': 
     left, index = parse_paren(tokens, index) 
    elif token.name == 'SYMBOL': 
     left, index = parse_symbol(tokens, index) 

    op = tokens[index] 
    index += 1 
    if not op.name == 'OR' and not op.name == 'AND': 
     raise 

    while True: 
     token = tokens[index] 
     if token.name == 'LPAREN': 
      right, index = parse_paren(tokens, index) 
     elif token.name == 'SYMBOL': 
      right, index = parse_symbol(tokens, index) 

     op = eval_or if op.name == 'OR' else eval_and 
     result = op(left, right) 

     continue_ = False 
     if not index == len(tokens): 
      next_ = tokens[index] 
      if next_.name == 'OR' or next_.name == 'AND': 
       continue_ = True 
       op = next_ 

     if continue_: 
      left = result 
      index += 1 
      continue 
     else: 
      return (result, index) 

def parse(tokens): 
    result = None 

    token = tokens[0] 
    if token.name == 'LPAREN': 
     result, _ = parse_paren(tokens, 0) 
    else: 
     result, _ = parse_expr(tokens, 0) 

    return result 

for s in [s1, s2, s3]: 
    print parse(tokenize(s)) 

Der Ausgang ist

[['A', 'C'], ['A', 'D'], ['B', 'C'], ['B', 'D']] 
[['A', 'B', 'D', 'E'], ['A', 'C', 'D', 'E']] 
[['A'], ['B', 'C'], ['D'], ['E']] 

Answer 2

Für die rekursive Natur des Ausdrucks können Sie das Element Forward verwenden, und für die Klauseln variabler Länge können Sie ZeroOrMore verwenden. Auf der Basis Ihrer bestehenden Grammatik:

expression = pp.Forward() 
atom = gene_id | pp.Group(l_brackets + expression + r_brackets) 
expression << atom + pp.ZeroOrMore(logical + expression) 

Damit expression.parseString Ergebnisse in der folgenden für Ihre Eingabe Strings:

[['(', ['(', 'A', 'OR', 'B', ')'], 'AND', ['(', 'C', 'OR', 'D', ')'], ')'], 'OR', 'E'] 
[['(', 'A', 'AND', ['(', 'B', 'OR', 'C', ')'], 'AND', 'D', 'AND', 'E', ')']] 
['A', 'OR', ['(', 'B', 'AND', 'C', ')'], 'OR', 'D', 'OR', 'E'] 

Wenn Sie der ( und ) in der Ausgabe, um loszuwerden, sollten Sie Rufen Sie suppress() auf l_bracket und r_bracket. Angesichts der Gruppierung (mit Group) werden diese nicht wirklich benötigt. Die Ausgabe ist dann z. B. [['A', 'AND', ['B', 'OR', 'C'], 'AND', 'D', 'AND', 'E']] für Ihre zweite Zeichenfolge.

Die conversion to DNF ist eine andere Frage und sollte am besten in einer anderen Frage gestellt werden.