Python：將邏輯字符串解析爲列表的列表

Question

我從數據庫中獲取一串邏輯表達式，並且需要將這些字符串放入列表以供進一步評估。我已經嘗試了很多關於字符串解析的內容，但到目前爲止還找不到答案。對於這個問題更容易理解，這裏有3個例子：

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' 

預期輸出繼電器：

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'] ] 

所以基本上我需要完全工廠化表達式的OR方面，把那些進入名單。這意味着任何AND條件通過使兩個表達式在相同的sublist中表達，而任何OR條件觸發創建新的子列表。

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

來自數據庫的字符串具有任意長度和任意數量的括號。

任何人都知道如何定義語法，這樣我就可以使用例如pyparsing包？

語法的開始到目前爲止是：

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') 

但是我怎麼都定義真正的解析器？

其中一個主要問題是我不知道如何處理任意發生的括號和字符串的長度變化。我一直在玩pyparser工具箱中的nestedExpr()-parser，但目前無法創建正確的行爲。

Answer 1

這是一個解決方案，它使用標記器和遞歸下降解析器給出您期望的結果。不幸的是，我不熟悉pyparsing庫，所以我沒有使用它。

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)) 

輸出是

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

Answer 2

對於表達式的遞歸性質，可以使用Forward元素，對於可變長度子句，可以使用ZeroOrMore。根據您現有的語法：

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

有了這個，expression.parseString結果在您的輸入字符串如下：

[['(', ['(', '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'] 

如果你想擺脫在輸出(和)，你應該請致電suppress()，電話l_bracket和r_bracket。鑑於分組（Group）這些並不是真的需要。然後輸出將是，例如，[['A', 'AND', ['B', 'OR', 'C'], 'AND', 'D', 'AND', 'E']]爲您的第二個字符串。

conversion to DNF是另一回事，最好在另一個問題中提出。