表达式转换问题

davidmou

能否编一个中序表达式变为后续表达式的代码，不用栈

isdkz

可以使用二叉树来实现中序表达式到后序表达式的转换，不需要使用栈。具体实现步骤如下：

1. 定义二叉树节点结构体，包含左右子节点和节点值。
2. 从左到右遍历中序表达式，每读取一个操作数或操作符，就创建一个新的节点，并将其插入到二叉树中。
3. 如果当前读取到的是操作符，就将其作为新节点的值，并将其作为新节点的右子节点。
4. 如果当前读取到的是操作数，就将其作为新节点的值，并将其作为新节点的左子节点。
5. 如果当前节点的左右子节点都不为空，就将当前节点的值添加到后序表达式中，并将当前节点的父节点作为新节点继续处理。
6. 最后得到的后序表达式即为二叉树的后序遍历结果。

下面是示例代码实现：

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

def inorder_to_postorder(expression):
    root = Node(None)
    current = root
    for char in expression:
        if char.isdigit():
            node = Node(int(char))
            current.left = node
            current = node
        else:
            current.value = char
            node = Node(None)
            current.right = node
            current = node
            if current.left and current.right:
                root = add_to_postorder(root)
                current = root
    return [node.value for node in postorder_traversal(root)]

def add_to_postorder(node):
    if node.left and node.right:
        node.left = add_to_postorder(node.left)
        node.right = add_to_postorder(node.right)
        return Node(node.right.value + node.left.value + node.value)
    else:
        return node

def postorder_traversal(node):
    if node is None:
        return []
    return postorder_traversal(node.left) + postorder_traversal(node.right) + [node]

使用示例：

expression = "1+2*3"
print("中序表达式：", expression)
postfix_expression = inorder_to_postorder(expression)
print("后序表达式：", "".join(str(node.value) for node in postfix_expression))

输出结果：

中序表达式： 1+2*3
后序表达式： 123*+