Parsing and computing boolean set definitions

Question

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

S = '(A or B) and not(A and 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}

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

Answer 1

What I would do is to use the shunting yard algorithm to convert this to Reverse Polish Notation and then use this simple algorithm to evaluate the espression.

No need for a proper parser then, you only need to recognize each word, parens and special character composing the definition with no need of "understanding the structure of the sentence".

Answer 2

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)'.

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

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