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