解析和计算布尔集定义 [英] Parsing and computing boolean set definitions

问题描述

说我有一组取值定义为一个字符串，例如如下：

Say I have a set S defined as a string, e.g. as follows:

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

，其中A，B和C是有限集，例如：

where A, B and C are finite sets, e.g.:

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

如果我们分析取值一步一步，我们有：

If we analyze S step by step, we have:

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

这让我们最终的结果是：

which gives us the final result:

S = {0,2}

我怎么能计算 S的元素给出其定义为一般布尔公式？

How can I compute the elements of S given its definition as a general boolean formula?

我不太知道如何着手解决这个问题。一方面，我不知道如果我需要使用一个完整的词法分析器。此外，一些阅读后，我还发现了两个概念似乎是高度相关的，但不知道他们会如何申请：

I don't quite know how to start addressing this problem. On one hand I wonder if I need to use a full lexical parser. Also, after some reading I also found two concepts that seem that highly related, but don't know how they would apply:

• 典型范式


• 德摩根定律

• Canonical Normal Forms
• De Morgan's laws

推荐答案

有没有必要，如果你愿意到适合的字符串变换的取值的有<写自己的解析器A HREF =htt​​p://docs.python.org/2.7/library/functions.html#eval> 的eval（）的。变化的取值的从（A或B），而不是（A和C）成等价的 T 的使用Python的的在的 - 运算符（X在A或B中x）和非（X在A和X在C）。

There is no need to write your own parser if you're willing to transform S in to a string suitable for use with eval(). Change S from '(A or B) and not(A and C)' into an equivalent T that uses Python's in-operator '(x in A or x in B) and not(x in A and x in C)'.

计算通过遍历元素的宇宙和测试它们是否匹配上述前pression的结果。
下面是在交互式提示符下制定出例如：

Compute the result by looping over the universe of elements and testing whether they match the above expression. Here's a worked-out example at the interactive prompt:

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

要自动进行改造，创造了一系列变量，其中变量查找做一套成员测试命名空间。全部放在一起给你一个简单而干净的一套-EX pression评估：

To make the transformation automatically, create a namespace for the set variables where variable lookups do a set membership test. Putting it all together gives you a simple and clean set-expression evaluator:

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

希望这会解决您的问题，不必编写自己的解析器，为您节省： - ）

Hope this solves your problem and saves you from having to write your own parser :-)

这篇关于解析和计算布尔集定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！