数据结构编写一个程序,先用二又树来表示一个简单算术表达式,数的每一个结点包括一个运算符或运算数。在简单算术表达式中包含+,-,*,/ 和一位正整数且格式正确,并且要按照先乘除后加减的原则构造二叉树,然后由对应的二又树计算该表达式的值。
时间: 2024-12-19 22:15:38 浏览: 13
为了实现这个程序,我们可以使用Python语言,因为它的语法简洁,非常适合描述这个问题。首先,我们需要定义一个节点类`Node`,用于存储运算符和操作数。接着,我们创建一个`ExpressionTree`类,用于构建二叉树并执行计算。
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# 根据运算符优先级定义一个辅助函数
def priority(op):
if op == '+' or op == '-':
return 1
elif op == '*' or op == '/':
return 2
else:
return 0
# 构建二叉树函数
def build_expression_tree(expression):
tokens = expression.split()
if len(tokens) == 1: # 如果只有一个数字,直接返回节点
return Node(int(tokens[0]))
root = Node(tokens[0])
i = 1
while i < len(tokens):
left = build_expression_tree(' '.join(tokens[i:i + 2])) # 分配左子树
right = build_expression_tree(' '.join(tokens[i + 2:])) # 分配右子树
if priority(tokens[i]) > priority(tokens[i + 1]):
root.left = left
root.right = right
else:
root.left = right
root.right = left
i += 3 # 跳过已处理的部分
return root
# 计算表达式值的递归函数
def calculate(node):
if node.value.isdigit():
return int(node.value)
else:
left_val = calculate(node.left)
right_val = calculate(node.right)
if node.value == '+':
return left_val + right_val
elif node.value == '-':
return left_val - right_val
elif node.value == '*':
return left_val * right_val
else: # '/' 表示除法
return left_val / right_val
# 示例表达式计算
expression = "3 + 5 * 2"
tree = build_expression_tree(expression)
result = calculate(tree)
print(f"表达式 {expression} 的结果是:{result}")
阅读全文