用python设计一个使用二叉树实现数学表达式求值的程序,需要完成以下功能: (1)输入一个中缀表达式,建立二叉解析树,并对其进行先序、中序和后序的遍历;
时间: 2024-03-14 20:47:40 浏览: 140
好的,我可以为您提供一个 Python 实现的基于二叉树的数学表达式求值程序。
代码如下:
```python
class Node:
def __init__(self, value=None):
self.left = None
self.right = None
self.value = value
def __str__(self):
return str(self.value)
def build_tree(expression):
operator_stack = []
operand_stack = []
operators = set(['+', '-', '*', '/', '(', ')'])
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
for i in expression:
if i == '(':
operator_stack.append(i)
elif i == ')':
while operator_stack[-1] != '(':
op = operator_stack.pop()
r = operand_stack.pop()
l = operand_stack.pop()
node = Node(op)
node.left = l
node.right = r
operand_stack.append(node)
operator_stack.pop()
elif i not in operators:
operand_stack.append(Node(i))
else:
while operator_stack and operator_stack[-1] != '(' and precedence[i] <= precedence[operator_stack[-1]]:
op = operator_stack.pop()
r = operand_stack.pop()
l = operand_stack.pop()
node = Node(op)
node.left = l
node.right = r
operand_stack.append(node)
operator_stack.append(i)
while operator_stack:
op = operator_stack.pop()
r = operand_stack.pop()
l = operand_stack.pop()
node = Node(op)
node.left = l
node.right = r
operand_stack.append(node)
return operand_stack.pop()
def preorder(node):
if node:
print(node, end=' ')
preorder(node.left)
preorder(node.right)
def inorder(node):
if node:
inorder(node.left)
print(node, end=' ')
inorder(node.right)
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node, end=' ')
def evaluate(node):
if node.left is None and node.right is None:
return int(node.value)
left_val = evaluate(node.left)
right_val = evaluate(node.right)
operator = node.value
if operator == '+':
return left_val + right_val
elif operator == '-':
return left_val - right_val
elif operator == '*':
return left_val * right_val
elif operator == '/':
return left_val / right_val
expression = input('请输入中缀表达式:')
tree = build_tree(expression)
print('先序遍历结果:', end='')
preorder(tree)
print()
print('中序遍历结果:', end='')
inorder(tree)
print()
print('后序遍历结果:', end='')
postorder(tree)
print()
print('表达式的值为:', evaluate(tree))
```
程序运行时,您需要输入一个中缀表达式,例如:`3 + 4 * (2 - 1)`,然后程序会根据中缀表达式构建二叉树,并输出先序、中序和后序遍历结果以及表达式的值。
希望这个程序能够帮助到您!
阅读全文