如何评估这棵解析树的最终结果？

Question

我正在尝试评估解析树的最终结果（True 或 False）。在这样的树中，节点对应于逻辑运算符（AND 或 OR），而叶子对应于 True 或 False 的原子条件。我用嵌套列表表示我的树：

# Generic class from which all operators derive
class Node(list):
    @property
    def label(self):
        return self.__class__.__name__

    def __repr__(self):
        
        return self.label + super().__repr__()

# Subclass for each operator
class AND(Node):
     pass
class OR(Node):
     pass

解析和评估原子条件后，我得到以下内容 object：

AND[OR[AND[True, True], AND[False, True, False], AND[True, True, AND[True, False]]], AND[True, True, True, False], OR[True, False]]

当然，对于AND节点，所有条件都必须为真。对于 OR 条件，只有一个必须为真。最后，我想得到最终结果，True 或 False 是合并所有这些 sub-conditions.

的结果

这是我为实现此逻辑而编写的代码：

def evaluate(root, parent = None):
    
    if(depth(root) == 0):
        return root
    if depth(root) > 1:
        return root.__class__(evaluate(item, root) for item in root)
    elif depth(root) == 1:
        operator = root.label
        if(operator == "AND"):
            if False not in root:
                return True
        if(operator == "OR"):
            if True in root:
                return True
        return False

我的主要功能只是调用 evaluate(result)

我得到的结果是：

AND[OR[True, False, AND[True, True, False]], False, True]

我认为我现在需要的是在评估一个child的结果之后做一些反向DFS。就像解构嵌套列表以在最后得到最终结果。

有什么建议吗？

Answer 1

在您现有的 evaluate 函数中，这就是问题所在 -

    if depth(root) > 1:
        return root.__class__(evaluate(item, root) for item in root)

在每个节点，我们应该在该节点的子节点返回的值上使用 operator。

这是 evaluate 函数对应的 psuedo-code（我无法测试它，因为问题中缺少完整的 class 定义）

def evaluate(root):
    if(depth(root) == 0):
        # would we ever go in this block?
        return root
    elif depth(root) == 1:
        operator = root.label
        if(operator == "AND"):
            return all(root)
        elif(operator == "OR"):
            return any(root)
        return False

    # depth(root) > 1
    if root.label == "AND":
        return all(evaluate(child) for child in root)
    elif root.label == "OR"
        return any(evaluate(child) for child in root)

使用 all() 和 any() 将有助于 short-circuiting 尽早进行评估，以防我们遇到在给定节点处得出明确答案的子树。

如何评估这棵解析树的最终结果？

How to evaluate the final result of this parse tree?

python

algorithm

tree

parsing