确定布尔表达式中导致计算结果为True的相关部分

问题描述

假设我有一个布尔表达式，我知道这些表达式的计算结果为True，其中有多个变量(1.n)是True，那么如何确定哪些True值对表达式有实际影响(即使其计算结果为True)？

基本示例：假设我有(A and B) or (C and D)withA = True、B = True和C = True。在这种情况下，C的值与布尔表达式的求值无关，因为给定D = False时，表达式的右侧始终求值为false。

我需要一个方法(例如find_relevant_values())来确定[A, B]是否相关。

A = True
B = True
C = True
D = False
bool_exp = "(A and B) or (C and D)"
print(eval(bool_exp)) #True

# is this doable?
print(find_relevant_values(bool_exp)) #[A, B]

我需要一种通用的方法(例如find_relevant_values())来确定相关的值。上例中[A, B]为相关值。

---

解决方案

下面的解决方案分为三个步骤：首先，解析输入字符串，生成表达式树。其次，遍历树以查找or运算符的任何实例。如果任何or操作数的计算结果为True，则该操作数要么是终结值(A、B、C或D)，要么由find_relevant递归遍历。最后，如果未找到or运算符，则计算整个表达式，如果结果为True，则遍历树以查找触发True值的所有相关表达式：

import re, collections as cl
m, op = {'A':True, 'B':True, 'C':True, 'D':False}, {'or':lambda x, y:x or y, 'and':lambda x, y:x and y}
#create the expression tree
def parse_expr(d):
   while (n:=next(d, None)) not in {None, ')'}:
     if n != '(':
        yield n
     else:
        yield list(parse_expr(d))

#evaluate the tree
def rel_eval(expr):
   while len(expr) > 1:
      _a, b, _c = [expr.popleft() for _ in range(3)]
      a = m.get(_a, _a) if not isinstance(_a, list) else rel_eval(collections.deque(_a))
      c = m.get(_c, _c) if not isinstance(_c, list) else rel_eval(collections.deque(_c))
      expr.appendleft(op[b](a, c))
   return expr[0]

#search for the relevant parts of the expression
def find_relevant(d):
   f = False
   for i in range(len(d)-1):
      if d[i] == 'or':
         f = True
         if (isinstance(d[i-1], list) and rel_eval(cl.deque(d[i-1]))) or (not isinstance(d[i-1], list) and m.get(d[i-1], False)):
             yield from ([d[i-1]] if not isinstance(d[i-1], list) else find_relevant(d[i-1]))
             break
         elif (isinstance(d[i+1], list) and rel_eval(cl.deque(d[i+1]))) or (not isinstance(d[i+1], list) and m.get(d[i+1], False)):
             yield from ([d[i+1]] if not isinstance(d[i+1], list) else find_relevant(d[i+1]))
             break
   if not f and rel_eval(cl.deque(d)):
      for i in filter(lambda x:x != 'and' and x != 'or', d):
          yield from ([i] if not isinstance(i, list) else find_relevant(i))
       

---

放在一起：

def find_relevant_values(s):
   #parse the input and create the tree
   r = list(parse_expr(iter(re.findall('(|)|w+', s))))
   #consume the generator results from find_revelant
   return list(find_relevant(r))

print(find_relevant_values('(A and B) or (C and D)'))
print(find_relevant_values('(A and (B or C)) and (C or D)'))

输出：

['A', 'B']
['A', 'B', 'C']