二叉树实现简易计算器

二叉树可以用来实现简易计算器，具体实现方法如下：

1.定义二叉树节点类，包含数字和运算符两种类型的节点。

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

2.定义一个函数，将输入的字符串转换为二叉树。

def buildTree(s, start, end):
    if start > end:
        return None
    if start == end:
        return TreeNode(int(s[start]))
    i = start
    while i <= end:
        if s[i] == '+' or s[i] == '-' or s[i] == '*' or s[i] == '/':
            root = TreeNode(s[i])
            root.left = buildTree(s, start, i - 1)
            root.right = buildTree(s, i + 1, end)
            return root
        i += 1
    return None

3.定义一个函数，计算二叉树的值。

def calculate(root):
    if root.val == '+':
        return calculate(root.left) + calculate(root.right)
    elif root.val == '-':
        return calculate(root.left) - calculate(root.right)
    elif root.val == '*':
        return calculate(root.left) * calculate(root.right)
    elif root.val == '/':
        return calculate(root.left) / calculate(root.right)
    else:
        return root.val

4.将输入的字符串转换为二叉树，并计算二叉树的值。

s = "11+22*3-16/4"
root = buildTree(s, 0, len(s) - 1)
print(calculate(root)) # 输出：65.0