解析和计算布尔集合定义

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

我会使用一种叫做洗牌算法的方法，把这个表达式转换成逆波兰表示法，然后再用一个简单的算法来计算这个表达式。

这样就不需要一个复杂的解析器了，你只需要识别每个单词、括号和组成定义的特殊字符，而不需要“理解句子的结构”。

Answer 2

如果你愿意把 S 转换成一个适合用在 eval() 的字符串，就不需要自己写解析器。你可以把 S 从 '(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}
                  )

希望这能解决你的问题，免去你自己写解析器的麻烦 :-)