파이썬 : 논리 문자열을리스트 목록으로 구문 분석

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' 

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

그래서 기본적으로 내가 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') 

하지만 어떻게 내가 진짜 파서를 정의해야합니까 :

지금까지 문법의 시작은?

주요 문제 중 하나는 임의의 발생하는 대괄호와 문자열의 길이가 다른 방법을 처리하는 방법을 모르겠다는 것입니다. 나는 도구 상자에서 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 포함)는 실제로 필요하지 않습니다. 그러면 두 번째 문자열의 출력은 [['A', 'AND', ['B', 'OR', 'C'], 'AND', 'D', 'AND', 'E']]이됩니다.

conversion to DNF은 다른 문제이며 다른 질문에서 가장 잘 질문해야합니다.