解析和计算布尔集定义

Question

假设我有一个S定义为字符串的集合,例如如下:

S = '(A or B) and not(A and C)'

其中A,B和C是有限集,例如:

A = {0, 1}
B = {0, 2}
C = {1, 3}

如果我们S逐步分析,我们有:

(A or B)   = {0, 1, 2}
(A & C)    = {1}
not(A & C) = {0, 2, 3}

这给了我们最终的结果:

S = {0,2}

如何计算S给定定义的元素作为一般布尔公式？

我不太清楚如何开始解决这个问题.一方面我想知道我是否需要使用完整的词法解析器.此外,经过一些阅读后,我还发现了两个看似高度相关的概念,但不知道它们将如何应用:

• 规范范式
• 德摩根的法律

Answer 1

如果您愿意将S转换为适合与eval()一起使用的字符串,则无需编写自己的解析器.更改小号从'(A or B) and not(A and C)'成等价的牛逼使用Python的中 -运算符'(x in A or x in B) and not(x in A and x in C)'.

通过循环遍历元素并测试它们是否与上述表达式匹配来计算结果.这是交互式提示中的一个经过实践证明的示例:

>>> T = '(x in A or x in B) and not(x in A and x in C)'
>>> sets = {'A': {0, 1}, 'B': {0, 2}, 'C': {1, 3}}
>>> universe = {x for s in sets.values() for x in s}
>>> {x for x in universe if eval(T, sets, {'x': x})}
set([0, 2])

要自动进行转换,请为设置变量创建命名空间,其中变量查找执行集合成员资格测试.将它们放在一起为您提供了一个简单而干净的set-expression评估器:

class SetVariables(dict):
    'Transform a variable lookup into a membership test'
    def __getitem__(self, var):
        s = dict.__getitem__(self, var)
        return self.x in s

def set_eval(expr, **sets):
    'Evaluation a set expression for the given sets'
    universe = {x for s in sets.values() for x in s}
    expr = compile(expr, '', 'eval')
    variables = SetVariables(sets)
    results = set()
    for x in universe:
        variables.x = x
        if eval(expr, {}, variables):
            results.add(x)
    return results

if __name__ == '__main__':
    print set_eval(expr = '(A or B) and not(A and C)',
                   A = {0, 1},
                   B = {0, 2},
                   C = {1, 3}
                  )

希望这能解决您的问题并使您免于编写自己的解析器:-)