Python:优化树评估器

Question

我知道树是一种经过深入研究的结构。

我正在编写一个程序，随机生成许多表达式树，然后按适合度属性进行排序和选择。

我有一个 MakeTreeInOrder() 类，它将树转换为“eval”可以计算的字符串。

但是它被调用了很多次，应该针对时间进行优化。

下面是一个构建树的函数，该树添加连续数字以用作测试。

我想知道是否有一种优化的方法来评估树结构中的表达式。我认为

它已被广泛使用并且已经有人这样做了。

import itertools
from collections import namedtuple 

#Further developing Torsten Marek's second suggestion

KS = itertools.count()
Node = namedtuple("Node", ["cargo", "args"]) 

def build_nodes (depth = 5):     
    if (depth <= 0): 
        this_node = Node((str(KS.next())), [None, None])
        return this_node 
    else:
        this_node = Node('+', []) 
        this_node.args.extend( 
          build_nodes(depth = depth - (i + 1))                             
          for i in range(2)) 

        return this_node

以下是我认为可以做得更快的代码。我希望得到一些想法。

class MakeTreeInOrder(object):
    def __init__(self, node):
        object.__init__(self)
        self.node = node
        self.str = ''
    def makeit(self, nnode = ''):
        if nnode == '':
            nnode = self.node
        if nnode == None: return
        self.str +='('
        self.makeit(nnode.args[0])
        self.str += nnode.cargo
        self.makeit(nnode.args[1])
        self.str+=')'
        return self.str

def Main():
    this_tree = build_nodes()
    expression_generator = MakeTreeInOrder(this_tree)
    this_expression = expression_generator.makeit()
    print this_expression
    print eval(this_expression)

if __name__ == '__main__':
    rresult = Main()

Answer 1

在这里添加一些面向对象的元素可以让事情变得更简单。为树中的每个事物创建 Node 子类，并使用“eval”方法评估它们。

import random

class ArithmeticOperatorNode(object):
    def __init__(self, operator, *args):
        self.operator = operator
        self.children = args
    def eval(self):
        if self.operator == '+':
            return sum(x.eval() for x in self.children)
        assert False, 'Unknown arithmetic operator ' + self.operator
    def __str__(self):
        return '(%s)' % (' ' + self.operator + ' ').join(str(x) for x in self.children)

class ConstantNode(object):
    def __init__(self, constant):
        self.constant = constant
    def eval(self):
        return self.constant
    def __str__(self):
        return str(self.constant)

def build_tree(n):
    if n == 0:
        return ConstantNode(random.randrange(100))
    else:
        left = build_tree(n - 1)
        right = build_tree(n - 1)
        return ArithmeticOperatorNode('+', left, right)

node = build_tree(5)
print node
print node.eval()

要评估树，只需在顶级节点上调用 .eval()。

node = build_tree(5)
print node.eval()

我还添加了一个 __str__ 方法来将树转换为字符串，这样您就可以看到它如何推广到其他树函数。目前它只是执行“+”，但希望它清楚如何将其扩展到所有算术运算。