python - Parsing and computing boolean set definitions -

say have set s defined string, e.g. follows:

s = '(a or b) , not(a , c)' 

where a, b , c finite sets, e.g.:

a = {0, 1} b = {0, 2} c = {1, 3} 

if analyze s step step, have:

(a or b)   = {0, 1, 2} (a & c)    = {1} not(a & c) = {0, 2, 3} 

which gives final result:

s = {0,2} 

how can compute elements of s given definition general boolean formula?

i don't quite know how start addressing problem. on 1 hand wonder if need use full lexical parser. also, after reading found 2 concepts seem highly related, don't know how apply:

• canonical normal forms
• de morgan's laws

there no need write own parser if you're willing transform s in string suitable use eval(). change s '(a or b) , not(a , c)' equivalent t uses python's in-operator '(x in or x in b) , not(x in , x in c)'.

compute result looping on universe of elements , testing whether match above expression. here's worked-out example @ interactive prompt:

>>> t = '(x in or x in b) , not(x in , x in c)' >>> sets = {'a': {0, 1}, 'b': {0, 2}, 'c': {1, 3}} >>> universe = {x s in sets.values() x in s} >>> {x x in universe if eval(t, sets, {'x': x})} set([0, 2]) 

to make transformation automatically, create namespace set variables variable lookups set membership test. putting gives simple , clean set-expression evaluator:

class setvariables(dict):     'transform variable lookup membership test'     def __getitem__(self, var):         s = dict.__getitem__(self, var)         return self.x in s  def set_eval(expr, **sets):     'evaluation set expression given sets'     universe = {x s in sets.values() x in s}     expr = compile(expr, '', 'eval')     variables = setvariables(sets)     results = set()     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) , not(a , c)',                    = {0, 1},                    b = {0, 2},                    c = {1, 3}                   ) 

hope solves problem , saves having write own parser :-)