Python：リストのリストに論理文字列を解析する

Question

データベースから論理式の文字列を取得し、それをさらに評価するためにリストに入れる必要があります。私はすでに文字列解析について多くのことを読んでみましたが、これまでのところ答えは見つかりませんでした。

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の面で完全に因数分解表現を必要とし、リストにそれらを入れて、問題の理解を容易にするため、ここでは3例があります。つまり、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') 

しかし、どのように、私は本当のパーサを定義する必要がありますか？

大きな問題の1つは、任意の括弧や文字列の長さの変化を処理する方法がわかりません。私は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'] 

あなたは出力に(と)を取り除きたい場合は、あなたがすべき既存の文法に基づいて、 l_bracketとr_bracketにsuppress()と電話してください。グループ分け（Group）があれば、それらは本当に必要ではありません。 2番目の文字列の出力は、たとえば[['A', 'AND', ['B', 'OR', 'C'], 'AND', 'D', 'AND', 'E']]になります。

conversion to DNFは別の問題であり、別の質問で最もよく質問する必要があります。