Динамическая оценка простой логической логики в Python

Question

У меня есть несколько динамически генерируемых логических логических выражений, например:

• (A или B) и (C или D)
• А или (А и Б)
• А
• пусто - оценивается как True

Заполнители заменяются логическими значениями.Нужно ли мне,

1. Преобразуйте эту информацию в выражение Python, например True or (True or False) и eval это?
2. Создайте двоичное дерево, где узел является либо bool или Conjunction/Disjunction объект и рекурсивно оценить его?
3. Преобразовать его во вложенные S-выражения и использовать парсер Lisp?
4. Что-то другое?

Предложения приветствуются.

Answer 1

Совсем нетрудно написать оценщик, который сможет справиться с этим, например, используя пипарсинг.Вам нужно обработать всего несколько операций (и, или, и группировку?), поэтому вы сможете самостоятельно их проанализировать и оценить.

Вам не нужно явно формировать двоичное дерево для вычисления выражения.

Answer 2

Вот небольшой (возможно, 74 строки, включая пробелы) модуль, который я построил примерно за полтора часа (плюс почти час на рефакторинг):

str_to_token = {'True':True,
                'False':False,
                'and':lambda left, right: left and right,
                'or':lambda left, right: left or right,
                '(':'(',
                ')':')'}

empty_res = True


def create_token_lst(s, str_to_token=str_to_token):
    """create token list:
    'True or False' -> [True, lambda..., False]"""
    s = s.replace('(', ' ( ')
    s = s.replace(')', ' ) ')

    return [str_to_token[it] for it in s.split()]


def find(lst, what, start=0):
    return [i for i,it in enumerate(lst) if it == what and i >= start]


def parens(token_lst):
    """returns:
        (bool)parens_exist, left_paren_pos, right_paren_pos
    """
    left_lst = find(token_lst, '(')

    if not left_lst:
        return False, -1, -1

    left = left_lst[-1]

    #can not occur earlier, hence there are args and op.
    right = find(token_lst, ')', left + 4)[0]

    return True, left, right


def bool_eval(token_lst):
    """token_lst has length 3 and format: [left_arg, operator, right_arg]
    operator(left_arg, right_arg) is returned"""
    return token_lst[1](token_lst[0], token_lst[2])


def formatted_bool_eval(token_lst, empty_res=empty_res):
    """eval a formatted (i.e. of the form 'ToFa(ToF)') string"""
    if not token_lst:
        return empty_res

    if len(token_lst) == 1:
        return token_lst[0]

    has_parens, l_paren, r_paren = parens(token_lst)

    if not has_parens:
        return bool_eval(token_lst)

    token_lst[l_paren:r_paren + 1] = [bool_eval(token_lst[l_paren+1:r_paren])]

    return formatted_bool_eval(token_lst, bool_eval)


def nested_bool_eval(s):
    """The actual 'eval' routine,
    if 's' is empty, 'True' is returned,
    otherwise 's' is evaluated according to parentheses nesting.
    The format assumed:
        [1] 'LEFT OPERATOR RIGHT',
        where LEFT and RIGHT are either:
                True or False or '(' [1] ')' (subexpression in parentheses)
    """
    return formatted_bool_eval(create_token_lst(s))

Простые тесты дают:

>>> print nested_bool_eval('')
True
>>> print nested_bool_eval('False')
False
>>> print nested_bool_eval('True or False')
True
>>> print nested_bool_eval('True and False')
False
>>> print nested_bool_eval('(True or False) and (True or False)')
True
>>> print nested_bool_eval('(True or False) and (True and False)')
False
>>> print nested_bool_eval('(True or False) or (True and False)')
True
>>> print nested_bool_eval('(True and False) or (True and False)')
False
>>> print nested_bool_eval('(True and False) or (True and (True or False))')
True

[Возможно частично не по теме]

Обратите внимание: вы можете легко настроить используемые вами токены (как операнды, так и операторы) с помощью предоставленных средств внедрения зависимостей для бедных (token_to_char=token_to_char и друзья), чтобы одновременно иметь несколько разных оценщиков (простой сброс глобальных переменных, «вставленных по умолчанию», оставит вас с единственным поведением).

Например:

def fuzzy_bool_eval(s):
    """as normal, but:
    - an argument 'Maybe' may be :)) present
    - algebra is:
    [one of 'True', 'False', 'Maybe'] [one of 'or', 'and'] 'Maybe' -> 'Maybe'
    """
    Maybe = 'Maybe' # just an object with nice __str__

    def or_op(left, right):
        return (Maybe if Maybe in [left, right] else (left or right))

    def and_op(left, right):
        args = [left, right]

        if Maybe in args:
            if True in args:
                return Maybe # Maybe and True -> Maybe
            else:
                return False # Maybe and False -> False

        return left and right

    str_to_token = {'True':True,
                    'False':False,
                    'Maybe':Maybe,
                    'and':and_op,
                    'or':or_op,
                    '(':'(',
                    ')':')'}

    token_lst = create_token_lst(s, str_to_token=str_to_token)

    return formatted_bool_eval(token_lst)

дает:

>>> print fuzzy_bool_eval('')
True
>>> print fuzzy_bool_eval('Maybe')
Maybe
>>> print fuzzy_bool_eval('True or False')
True
>>> print fuzzy_bool_eval('True or Maybe')
Maybe
>>> print fuzzy_bool_eval('False or (False and Maybe)')
False

Answer 3

Если вы настроили словари с локальными и глобальными объектами, которые вам интересны, вы сможете безопасно передать их вместе с выражением в eval().

Answer 4

Звучит как кусок пирога с использованием логического модуля SymPy.У них даже есть пример этого в документах: http://docs.sympy.org/0.7.1/modules/logic.html

Answer 5

Я пишу это, потому что сегодня мне нужно было решить аналогичную проблему, и я был здесь, когда искал подсказки.(Булев анализатор с произвольными строковыми токенами, которые позже преобразуются в логические значения).

Рассмотрев разные варианты (реализовать решение самому или использовать какой-то пакет), я остановился на Lark, https://github.com/lark-parser/lark

Его легко использовать и он работает довольно быстро, если вы используете LALR(1).

Вот пример, который может соответствовать вашему синтаксису

from lark import Lark, Tree, Transformer

base_parser = Lark("""
    expr: and_expr
        | or_expr
    and_expr: token
            | "(" expr ")"
            | and_expr " " and " " and_expr
    or_expr: token
            | "(" expr ")"
            | or_expr " " or " " or_expr
    token: LETTER
    and: "and"
    or: "or"
    LETTER: /[A-Z]+/
""", start="expr")


class Cleaner(Transformer):
    def expr(self, children):
        num_children = len(children)
        if num_children == 1:
            return children[0]
        else:
            raise RuntimeError()

    def and_expr(self, children):
        num_children = len(children)
        if num_children == 1:
            return children[0]
        elif num_children == 3:
            first, middle, last = children
            return Tree(data="and_expr", children=[first, last])
        else:
            raise RuntimeError()

    def or_expr(self, children):
        num_children = len(children)
        if num_children == 1:
            return children[0]
        elif num_children == 3:
            first, middle, last = children
            return Tree(data="or_expr", children=[first, last])
        else:
            raise RuntimeError()


def get_syntax_tree(expression):
    return Cleaner().transform(base_parser.parse(expression))

print(get_syntax_tree("A and (B or C)").pretty())

Примечание:выбранное мной регулярное выражение намеренно не соответствует пустой строке (Lark по какой-то причине этого не позволяет).