Computing the sum of a binary tree-CodePudding

Hi this code should compute a binary three and output 45. The issue is that var expression is reset before outputting. Too compute the sum use could be used 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

CodePudding user response：

Don't use global; it makes it very hard to keep your state from getting overwritten. You can do this with a very simple recursive function instead:

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

If you want it to produce the string form of the expression as well, make that part of the return value instead of using side effects:

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