将算术表达式((a+b)+c*(d+e)+f)*(g+h)转

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

def construct_expression_tree(expression):
    stack = []
    i = 0
    while i < len(expression):
        if expression[i] == '(':
            i += 1
            stack.append('(')
        elif expression[i] == ')':
            i += 1
            stack.pop()
        elif expression[i] in {'+', '*'}:
            node = TreeNode(expression[i])
            if stack and stack[-1] in {'+', '*'}:
                node.right = stack.pop(-1)
                node.left = stack.pop(-1)
            stack.append(node)
            i += 1
        else:
            j = i
            while j < len(expression) and expression[j].isalpha():
                j += 1
            operand = expression[i:j]
            stack.append(TreeNode(operand))
            i = j

    return stack.pop()

def prefix_expression(root):
    if root:
        print(root.val, end=' ')
        prefix_expression(root.left)
        prefix_expression(root.right)

def postfix_expression(root):
    if root:
        postfix_expression(root.left)
        postfix_expression(root.right)
        print(root.val, end=' ')

expression = "((a+b)+c*(d+e)+f)*(g+h)"
root = construct_expression_tree(expression)

print("前缀表达式：", end='')
prefix_expression(root)
print("\n后缀表达式：", end='')
postfix_expression(root)