使用Python在逻辑字符串中获取"AND"中的元素

Question

我想解析逻辑字符串并获得"和"逻辑中所有元素的组合.例如,对于字符串'(A和(B或C))'我应该得到[[A,B],[A,C]]和字符串'(A和B以及(C或D和F)或者F和G)'我应该[[A,B,C],[A,B,D,F],[F,G]].

我正在尝试使用pyparsing.在这篇文章之后,在这里以二叉树方式解析pyparsing中的复杂逻辑表达式,我设法得到一个嵌套列表,其中字母按照首选项分组("和"优先于"或",括号覆盖此):

import pyparsing as pp

complex_expr = pp.Forward()
vars = pp.Word(pp.alphas, pp.alphanums + "_") | pp.Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?").setName('proteins')
clause = pp.Group(vars ^ (pp.Suppress("(") + complex_expr + pp.Suppress(")") ))

expr = pp.operatorPrecedence(clause,[
                            ("and", 2, pp.opAssoc.LEFT, ),
                            ("or", 2, pp.opAssoc.LEFT, ),])
#print expr
complex_expr << expr
parseresult=complex_expr.parseString('( A and B and ( C or D and F ) or F and G )')
print parseresult

这使:

[[[['A'],'和',['B'],'和',[[['C'],'或',[['D'],'和',['F ']]]]],'或',[['F'],'和',['G']]]]]

现在我该如何处理这个结果来实现所需的输出？我会很乐意帮助你.我试过pyparsing但我对其他可能更好的模块开放.

提前致谢.

Answer 1

Python 库将为我们提供一些帮助：

import re
import itertools

我们来写一下需要的函数：

def analyse(expression):
    # Find all used symbols
    symbols = set(re.findall(r"\b[A-Z]\b", expression))
    # Find all combinations of symbols and values
    mappings = (dict(zip(symbols, values)) for values in itertools.product([False, True], repeat=len(symbols)))
    # Select combinations that make the whole expression true
    solutions = [sorted(name for name in mapping if mapping[name]) for mapping in mappings if eval(expression, None, mapping)]
    # Filter out redundant solutions
    return sorted(s1 for s1 in solutions if not any(set(s1) > set(s2) for s2 in solutions))

让我们测试一下：

assert analyse("( A and ( B or C ) )") == [["A", "B"], ["A", "C"]]
assert analyse("( A and B and ( C or D and F ) or F and G )") == [["A", "B", "C"], ["A", "B", "D", "F"], ["F", "G"]]

源码中有注释。无论如何，主要步骤是：

• 表达式变量被发现为单字符大写名称。
• 每个变量可以是 True 或 False。我们找到所有组合。
• 我们仅选择使整个表达式为 True 的组合。
• 我们只保留最小的解决方案，即那些不是其他解决方案的超集的解决方案。

我非常感谢你提出了一个很好的问题。Pythonitertools总是给我带来惊喜。;-)