计算二叉树的总和

Question

您好，此代码应计算二进制三并输出 45。问题是 var 表达式在输出前被重置。太计算和使用可以使用 eval(…)。

    def __init__(self, val, left = None, right = None):
        self.val=val
        self.left=left
        self.right=right
PLUS = "+"
MINUS = "-"
TIMES = "*"
DIVIDE = "/"

expression = ''
def evaluate(root, Node='M'): 
    global expression
    operators = (PLUS, MINUS, TIMES, DIVIDE)
    if root:
      evaluate(root.left, 'L')
      if root.val in operators or Node == 'M':
        a, b = '', ''
      elif Node == 'L':
        a, b = '(', ''
      elif Node == 'R':
        a, b = '', ')'
      expression += a+str(root.val)+b
      evaluate(root.right, 'R')
    else:
      print(expression, Node)
      return expression
    print(expression, Node)
#     *
#    / \
#   +    +
#  / \  / \
# 3  2  4  5
tree = Node(TIMES)
tree.left = Node(PLUS)
tree.left.left = Node(3)
tree.left.right = Node(2)
tree.right = Node(PLUS)
tree.right.left = Node(4)
tree.right.right = Node(5)      
print(evaluate(tree))
#45

Answer 1

不要使用global；这使得你的状态不被覆盖变得非常困难。您可以使用一个非常简单的递归函数来代替：

operators = {
    PLUS: int.__add__,
    MINUS: int.__sub__,
    TIMES: int.__mul__,
    DIVIDE: int.__floordiv__,
}


def evaluate(root: Node) -> int:
    if isinstance(root.val, int):
        return root.val
    return operators[root.val](
        evaluate(root.left),
        evaluate(root.right)
    )

tree = Node(TIMES)
tree.left = Node(PLUS)
tree.left.left = Node(3)
tree.left.right = Node(2)
tree.right = Node(PLUS)
tree.right.left = Node(4)
tree.right.right = Node(5)      
print(evaluate(tree))  # 45

如果您还希望它生成表达式的字符串形式，请将那部分作为 return 值而不是使用副作用：

def evaluate(root: Node) -> typing.Tuple[str, int]:
    if isinstance(root.val, int):
        return str(root.val), root.val
    le, ln = evaluate(root.left)
    re, rn = evaluate(root.right)
    return f"({le} {root.val} {re})", operators[root.val](ln, rn)

tree = Node(TIMES)
tree.left = Node(PLUS)
tree.left.left = Node(3)
tree.left.right = Node(2)
tree.right = Node(PLUS)
tree.right.left = Node(4)
tree.right.right = Node(5)      
print(*evaluate(tree), sep=" = ")  # ((3 + 2) * (4 + 5)) = 45

计算二叉树的总和

Computing the sum of a binary tree

python

python-3.x

binary-tree