表达式转换问题

davidmou

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

isdkz

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

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

下面是示例代码实现：

1. class Node:
   
2.     def __init__(self, value):
   
3.         self.left = None
   
4.         self.right = None
   
5.         self.value = value
   
6. 
   
7. def inorder_to_postorder(expression):
   
8.     root = Node(None)
   
9.     current = root
   
10.     for char in expression:
    
11.         if char.isdigit():
    
12.             node = Node(int(char))
    
13.             current.left = node
    
14.             current = node
    
15.         else:
    
16.             current.value = char
    
17.             node = Node(None)
    
18.             current.right = node
    
19.             current = node
    
20.             if current.left and current.right:
    
21.                 root = add_to_postorder(root)
    
22.                 current = root
    
23.     return [node.value for node in postorder_traversal(root)]
    
24. 
    
25. def add_to_postorder(node):
    
26.     if node.left and node.right:
    
27.         node.left = add_to_postorder(node.left)
    
28.         node.right = add_to_postorder(node.right)
    
29.         return Node(node.right.value + node.left.value + node.value)
    
30.     else:
    
31.         return node
    
32. 
    
33. def postorder_traversal(node):
    
34.     if node is None:
    
35.         return []
    
36.     return postorder_traversal(node.left) + postorder_traversal(node.right) + [node]
    

复制代码

使用示例：

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

复制代码

输出结果：

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

复制代码