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:
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as {0, 1}, or.
Boolean operators form the basis of mathematical sets and database logic. They connect your search words together to either narrow or broaden your set of results. The three basic boolean operators are: AND, OR, and NOT.
Boolean is a data type where the data only has two possible variables: true or false. In terms of computer science, Boolean is an identification classifier for working out logical truth values and algebraic variables.
There are three logical operators that are used to compare values. They evaluate expressions down to Boolean values, returning either True or False . These operators are and , or , and not and are defined in the table below.
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 :-)
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".
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With