How to evaluate the final result of this parse tree?-CodePudding

I am trying to evaluate the final result of a parse tree (either True or False). In such a tree, a node corresponds to a logical operator (AND or OR) whereas a leaf corresponds to an atomic condition that is either True or False. I am representing my tree with nested lists:

# 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

After parsing and evaluating the atomic conditions, I am getting the following object:

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

Of course, for an AND node, all of the conditions must be true. For OR conditions, only one must be true. At the end, I want to get the final result, True or False that results from the merging of all of this sub-conditions.

Here is the code that I wrote to implement this logic:

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

My main function is simply calling evaluate(result)

The result that I am getting is:

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

I think that what I need now is to do some reverse DFS after evaluating the result of a child. Like deconstructing the nested lists to get the final result at the end.

Any recommendations ?

CodePudding user response：

In your existing evaluate function, this is where the problem is -

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

At each node, we should be using the operator at the node on the value returned by the children of that node.

Here's the corresponding psuedo-code for the evaluate function(I can't test it since the full class definitions are missing in the question)

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)

The use of all() and any() would help in short-circuiting the evaluation early in case we come across a subtree which leads to a definite answer at the given node.