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

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

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

下面是一个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]