后缀表达式用二叉树计算的例子和代码
时间: 2024-05-16 16:17:47 浏览: 22
后缀表达式(也称为逆波兰表达式)可以用二叉树来计算。具体地,我们可以使用一个二叉树来表示后缀表达式,其中叶节点是操作数,内部节点是操作符,每个节点的左子树是该节点的第一个操作数,右子树是该节点的第二个操作数。通过遍历这个二叉树,我们可以计算出后缀表达式的值。
下面是一个用二叉树计算后缀表达式的例子:
假设我们有一个后缀表达式:`5 6 7 + *`,我们可以将它表示成下面的二叉树:
```
*
/ \
5 +
/ \
6 7
```
我们可以通过深度优先遍历这个二叉树来计算后缀表达式的值。具体来说,我们首先遍历左子树,然后遍历右子树,最后对根节点进行计算。对于每个节点,如果它是操作数节点,我们将它的值压入栈中;如果它是操作符节点,我们从栈中弹出两个操作数,执行相应的操作,然后将结果压回栈中。最终,栈顶元素就是后缀表达式的值。
下面是用 Python 实现后缀表达式计算的代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def eval_postfix(root):
if not root:
return 0
if not root.left and not root.right:
return int(root.val)
left_val = eval_postfix(root.left)
right_val = eval_postfix(root.right)
if root.val == '+':
return left_val + right_val
elif root.val == '-':
return left_val - right_val
elif root.val == '*':
return left_val * right_val
elif root.val == '/':
return left_val / right_val
def build_tree(postfix):
stack = []
for token in postfix:
if token.isdigit():
node = Node(token)
stack.append(node)
else:
right_node = stack.pop()
left_node = stack.pop()
node = Node(token)
node.left = left_node
node.right = right_node
stack.append(node)
return stack.pop()
postfix = '5 6 7 + *'.split()
root = build_tree(postfix)
print(eval_postfix(root)) # 输出 77
```
在这个实现中,我们首先定义了一个 `Node` 类来表示二叉树的节点。然后,我们实现了 `eval_postfix` 函数来计算后缀表达式的值。该函数通过递归遍历二叉树,对每个节点进行计算。最后,我们实现了 `build_tree` 函数来构建二叉树。该函数通过栈来实现,遍历后缀表达式中的每个 token,如果是操作数,则将其作为一个节点入栈;如果是操作符,则弹出栈顶的两个节点,构造一个新节点,将其左右子树分别设为这两个节点,然后将新节点入栈。最终,我们返回栈中唯一的节点,即二叉树的根节点。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)