输入简单算术表达式,利用二叉树表示,并在创建表达式树后求表达式的值
时间: 2023-12-14 17:40:26 浏览: 140
好的,我可以帮你实现这个功能。首先,我们需要将输入的算术表达式转换为表达式树。算术表达式可以通过中缀、前缀和后缀表示法来表示,其中后缀表示法也称为逆波兰表示法,是一种比较方便转换为表达式树的表示法。
下面是一个简单的算法,将输入的后缀表达式转换为表达式树:
1. 定义一个栈,用于存储操作数和操作符。
2. 从左到右遍历后缀表达式中的每个元素。
3. 如果是操作数,将其压入栈中。
4. 如果是操作符,弹出栈顶的两个操作数,并将它们作为当前操作符的左右子树,然后将新的子树压入栈中。
5. 遍历完后缀表达式后,栈中仅剩下一个元素,即为表达式树的根节点。
接下来,我们可以通过递归遍历表达式树,计算出表达式的值。具体实现可以参考下面的代码:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def build_expression_tree(postfix_expression):
stack = []
for token in postfix_expression:
if token.isdigit():
stack.append(Node(token))
else:
right = stack.pop()
left = stack.pop()
root = Node(token)
root.left = left
root.right = right
stack.append(root)
return stack.pop()
def evaluate_expression_tree(root):
if root.left is None and root.right is None:
return int(root.value)
left_value = evaluate_expression_tree(root.left)
right_value = evaluate_expression_tree(root.right)
if root.value == '+':
return left_value + right_value
elif root.value == '-':
return left_value - right_value
elif root.value == '*':
return left_value * right_value
elif root.value == '/':
return left_value / right_value
```
我们可以通过下面的代码测试这个功能:
```python
postfix_expression = '23+4*'
root = build_expression_tree(postfix_expression)
result = evaluate_expression_tree(root)
print(result) # 输出 14
```
在这个例子中,后缀表达式为 '23+4*',对应的表达式树如下所示:
```
*
/ \
+ 4
/ \
2 3
```
计算表达式的值时,我们先遍历左子树,得到 2+3=5,然后遍历右子树,得到 4,最后将它们相乘,得到 5*4=20,即为表达式的值。
阅读全文