在Python中动态评估简单的布尔逻辑

Question

我有一些动态生成的布尔逻辑表达式，例如：

• (A 或 B) 和 (C 或 D)
• A 或 (A 和 B)
• A
• 空 - 计算结果为 True

占位符被替换为布尔值。我应该

1. 将此信息转换为 Python 表达式，例如 True or (True or False) 和 eval 吗？
2. 创建一个二叉树，其中节点是 bool 或 Conjunction/Disjunction 对象并递归地评估它？
3. 将其转换为嵌套的 S 表达式并使用 Lisp 解析器？
4. 还有别的事吗？

欢迎提出建议。

Answer 1

这是我用大约一个半小时构建的一个小模块（可能有 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 2

编写一个可以处理此问题的评估器应该不难，例如使用 pyparsing。您只需处理一些操作（与、或和分组？），因此您应该能够自己解析和评估它。

您不需要显式地形成二叉树来计算表达式。

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 由于某种原因不允许这样做）。

Answer 6

您可以使用 Lark 语法库https://github.com/lark-parser/lark

from lark import Lark, Transformer, v_args, Token, Tree
from operator import or_, and_, not_

calc_grammar = f"""
    ?start: disjunction
    ?disjunction: conjunction
        | disjunction "or" conjunction   -> {or_.__name__}
    ?conjunction: atom
        | conjunction "and" atom  -> {and_.__name__}
    ?atom: BOOLEAN_LITTERAL           -> bool_lit
         | "not" atom         -> {not_.__name__}
         | "(" disjunction ")"
    BOOLEAN_LITTERAL: TRUE | FALSE
    TRUE: "True"
    FALSE: "False"
    %import common.WS_INLINE
    %ignore WS_INLINE
"""


@v_args(inline=True)
class CalculateBoolTree(Transformer):
    or_ = or_
    not_ = not_
    and_ = and_

    allowed_value = {"True": True, "False": False}

    def bool_lit(self, val: Token) -> bool:
        return self.allowed_value[val]


calc_parser = Lark(calc_grammar, parser="lalr", transformer=CalculateBoolTree())
calc = calc_parser.parse


def eval_bool_expression(bool_expression: str) -> bool:
    return calc(bool_expression)


print(eval_bool_expression("(True or False) and (False and True)"))
print(eval_bool_expression("not (False and True)"))
print(eval_bool_expression("not True or False and True and True"))

Answer 7

这可能是一个更简单的方法：

from sympy import symbols, simplify_logic

# Define symbolic variables
A, B, C, D = symbols('A B C D')

expr1 = '(A or B) and (C or D)'
expr2 = 'A or (A and B)'

def extractExpression(expr):
    expr = expr.replace('or', '|')
    expr = expr.replace('and', '&')
    expr = expr.replace('not', '~')
    return simplify_logic(expr)

expr1 = extractExpression(expr1)
expr2 = extractExpression(expr2)

expressions = [expr1, expr2]

inputs = [{A: True, B: True, C: True, D: False}, {A: False, B: True, C: True, D: False}]

# Evaluate the expression with specific values
for input in inputs:
    for expr in expressions:
        result = expr.subs(input)
        print("Simplified expression: ",expr)
        print('input: ',input)
        print('result: ', result)
        print()
        

输出：

Simplified expression:  (A & C) | (A & D) | (B & C) | (B & D)
input:  {A: True, B: True, C: True, D: False}
result:  True

Simplified expression:  A
input:  {A: True, B: True, C: True, D: False}
result:  True

Simplified expression:  (A & C) | (A & D) | (B & C) | (B & D)
input:  {A: False, B: True, C: True, D: False}
result:  True

Simplified expression:  A
input:  {A: False, B: True, C: True, D: False}
result:  False