设计算法将中缀表达式转换为表达式树

根据中缀表达式转换为表达式树的算法，可以分为以下步骤：

1. 创建一个空栈和一个空的表达式树。
2. 从左到右扫描中缀表达式中的每个元素。
3. 如果当前元素是操作数，则创建一个只包含该操作数的表达式树，并将其压入栈中。
4. 如果当前元素是操作符，则创建一个只包含该操作符的表达式树，并将其弹出栈两次，作为该操作符的左右子树，然后将该表达式树压入栈中。
5. 重复步骤2-4，直到扫描完整个中缀表达式。
6. 最后，栈中只剩下一个表达式树，即为所求的表达式树。

下面是一个Python实现的例子：

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

def infix_to_expression_tree(infix):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack = []
    for char in infix:
        if char.isalnum():
            node = TreeNode(char)
            stack.append(node)
        elif char in precedence:
            node = TreeNode(char)
            while stack and stack[-1].val != '(' and precedence[char] <= precedence[stack[-1].val]:
                node.right = stack.pop()
                node.left = stack.pop()
                stack.append(node)
            stack.append(node)
        elif char == '(':
            stack.append(TreeNode(char))
        elif char == ')':
            while stack and stack[-1].val != '(':
                node = stack.pop()
                if node.val in precedence:
                    node.right = stack.pop()
                    node.left = stack.pop()
                stack.append(node)
            stack.pop()
    while stack:
        node = stack.pop()
        if node.val in precedence:
            node.right = stack.pop()
            node.left = stack.pop()
        stack.append(node)
    return stack[0]