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

但是如何定义真正的解析器呢？你知道吗

其中一个主要的问题是我不知道如何处理任意出现的括号和不同长度的字符串。我一直在玩nestedExpr()-parser工具箱中的pyparser，但到目前为止还不能创建正确的行为。你知道吗

Answer 1

对于表达式的递归性质，可以使用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是另一回事，最好用另一个问题来问。你知道吗

Answer 2

下面是一个使用标记器和递归下降解析器给出所需结果的解决方案。不幸的是，我不熟悉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']]