利用二叉树写一个程序将算术表达式输入串(只要求1位整数)转换为后缀式,然后计算该表达式的值。要求: 1)从键盘或文件输入测试数据。 (2)输出算术表达式的后缀式和计算结果。
时间: 2023-06-27 08:05:05 浏览: 161
输入后缀表达式,即时生成对应的二叉树,计算出表达式的值,并且输出对应的前缀表达式、中缀表达式
以下是利用二叉树实现算术表达式转换为后缀式的 Python 代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def is_operator(char):
return char == '+' or char == '-' or char == '*' or char == '/'
def build_expression_tree(expression):
stack = []
for char in expression:
if is_operator(char):
right = stack.pop()
left = stack.pop()
node = TreeNode(char)
node.left = left
node.right = right
stack.append(node)
else:
node = TreeNode(char)
stack.append(node)
return stack.pop()
def inorder_traversal(root, postfix):
if root is None:
return
inorder_traversal(root.left, postfix)
if is_operator(root.val):
postfix.append(' ')
postfix.append(root.val)
if is_operator(root.val):
postfix.append(' ')
inorder_traversal(root.right, postfix)
def to_postfix(expression):
root = build_expression_tree(expression)
postfix = []
inorder_traversal(root, postfix)
return ''.join(postfix)
def calculate(expression):
postfix = to_postfix(expression)
stack = []
for char in postfix:
if char.isdigit():
stack.append(int(char))
elif char == '+':
right = stack.pop()
left = stack.pop()
stack.append(left + right)
elif char == '-':
right = stack.pop()
left = stack.pop()
stack.append(left - right)
elif char == '*':
right = stack.pop()
left = stack.pop()
stack.append(left * right)
elif char == '/':
right = stack.pop()
left = stack.pop()
stack.append(left / right)
return stack.pop()
```
接下来,我们可以使用该程序对测试数据进行测试,如下所示:
```python
expression = input("请输入算术表达式:")
postfix = to_postfix(expression)
print("后缀式为:", postfix)
result = calculate(expression)
print("计算结果为:", result)
```
注意,该程序只能处理一位整数的算术表达式,如果需要处理多位整数,请在构建二叉树时适当修改代码。
阅读全文