解析和计算布尔集定义

说我有一套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给出其作为一般布尔公式的定义？

我不太知道如何开始解决这个问题。一方面，我想知道是否需要使用完整的词法分析器。另外，经过一番阅读后，我还发现了两个似乎高度相关的概念，但不知道它们如何应用：

• 规范范式 http://en.wikipedia.org/wiki/Canonical_normal_form
• 德摩根定律 http://en.wikipedia.org/wiki/De_Morgan%27s_laws

如果您愿意进行改造，则无需编写自己的解析器S到适合使用的字符串eval() http://docs.python.org/2.7/library/functions.html#eval。改变S from '(A or B) and not(A and C)'转化为等价的T使用Python的in-操作员'(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])

要自动进行转换，请为集合变量创建一个命名空间，其中变量查找执行集合成员资格测试。将它们放在一起为您提供了一个简单而干净的集合表达式求值器：

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

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