CODEWITHSUNDEEP
pythonmathboolean
Ryan Adlob
Ryan Adlob

Reputation: 101

Reading equation from string and parsing it

I have boolean math expressions written in string form like this

"A and B or C and not D"
"A and (B or C) and not D"

I want to solve it using python, different functions will be called for "and", "or" and "and not" and "or not" operators. I can't come up with any ideas that can solve this.

I can break the equation with split but what's next ?

UPDATE: A and B and other can contain some words for which a list will be returned and on that list "and", "or" and other operations will be performed.

I have created that list and I can solve the 2 variable problem but how to solve it when it have multiple combinations.

Upvotes: 0

Views: 107

Answers (1)

JohanC
JohanC

Reputation: 80319

The symbol package Sympy seems to be a good choice.

In its basic form, sympy wants and, or and not written as &, | and ~, which can be replaced before calling the parser. Note that the simple string replacement wouldn't work well if there are names such as 'Brandon' which contain 'and'.

Afterwards, you can use sympy to do any kind of simplifications, manipulations and substitutions, just like any other mathematical expression.

An example:

from sympy.parsing.sympy_parser import parse_expr

str = "Alice and (Bob or Carla) and not David"
str = str.replace('and', '&').replace('or', '|').replace('not', '~')
expr = parse_expr(str)

print(expr)
print(expr.subs({'Alice': True, 'Bob': False}))

Output:

Alice & ~David & (Bob | Carla)
Carla & ~David

In the comments, you ask to operate on sets instead of on booleans. Sets of small numbers are represented in Sympy as FiniteSet. Normally, they need to be written using function notation: Union(arg1, arg2, arg3, ...). But we can make use of the boolean operators And, Or and Not which do allow infix notation to construct an expression and afterwards evaluate as if it were set operations.

from sympy.parsing.sympy_parser import parse_expr
from sympy import Atom, FiniteSet, And, Or, Not, Union, Intersection, Complement


def evaluate_expr(expr, replacements, complete_set):
    if isinstance(expr, Atom):
        return expr.subs(replacements)
    elif expr.func == Or:
        return Union(*[evaluate_expr(a, replacements, complete_set) for a in expr.args])
    elif expr.func == And:
        return Intersection(*[evaluate_expr(a, replacements, complete_set) for a in expr.args])
    elif expr.func == Not:
        return Complement(complete_set, evaluate_expr(expr.args[0], replacements, complete_set))

replacements = {'Alice': {1, 2}, 'Bob': {1, 2, 3}, 'Carla': {5}, 'David': {1, 4, 6}}
for r in replacements:
    # convert the replacements to their Sympy representation
    replacements[r] = FiniteSet(*replacements[r])
print("Replacements:", replacements)
complete_set = Union(*replacements.values()) # the set of all possible values is used to implement "not"

tests = ["Alice", "Alice or Bob", "Alice and Bob and Carla", "Alice and (Bob or Carla) and not David"]
for test in tests:
    expr = parse_expr(test.replace('and', '&').replace('or', '|').replace('not', '~'))
    print(expr)
    print(" --->", evaluate_expr(expr, replacements, complete_set))

Output:

Replacements: {'Alice': FiniteSet(1, 2), 'Bob': FiniteSet(1, 2, 3), 'Carla': FiniteSet(5), 'David': FiniteSet(1, 4, 6)}
Alice
 ---> FiniteSet(1, 2)
Alice | Bob
 ---> FiniteSet(1, 2, 3)
Alice & Bob & Carla
 ---> EmptySet
Alice & ~David & (Bob | Carla)
 ---> FiniteSet(2)

Upvotes: 1

Related Questions