用python编程,使 用 二 叉 树 计 算 公 式 的 真 值 。 首 先 , 利 用 堆 栈 将 公 式 的 中 缀 形 式 改 为 后 缀 形 式 。 其 次 , 根 据 后 缀 形 式 , 从 叶 节 点 构 造 相 应 的 二 叉 树 。 最 后 , 按 后 序 遍 历 二 叉 树 , 找 出 每 个 子 树 的 值 。
时间: 2024-02-14 22:06:29 浏览: 62
python 二叉树
好的,以下是用Python实现利用二叉树计算后缀表达式的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(postfix):
stack = []
for token in postfix:
if token.isdigit():
node = TreeNode(int(token))
stack.append(node)
else:
node = TreeNode(token)
node.right = stack.pop()
node.left = stack.pop()
stack.append(node)
return stack.pop()
def postorderTraversal(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
def evaluateTree(root):
if not root:
return 0
if not root.left and not root.right:
return root.val
left = evaluateTree(root.left)
right = evaluateTree(root.right)
if root.val == '+':
return left + right
elif root.val == '-':
return left - right
elif root.val == '*':
return left * right
else:
return int(left / right)
def infixToPostfix(infix):
stack = []
postfix = []
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
for token in infix:
if token.isdigit():
postfix.append(token)
elif token in precedence:
while stack and stack[-1] != '(' and precedence[token] <= precedence.get(stack[-1], 0):
postfix.append(stack.pop())
stack.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
postfix.append(stack.pop())
stack.pop()
while stack:
postfix.append(stack.pop())
return postfix
infix = input('请输入中缀表达式,数字和运算符之间请使用空格分隔:')
postfix = infixToPostfix(infix.split())
root = buildTree(postfix)
value = evaluateTree(root)
print('后缀表达式:', ' '.join(postfix))
print('二叉树后序遍历:', ' '.join(map(str, postorderTraversal(root))))
print('表达式的值为:', value)
```
在上面的代码中,`TreeNode`类表示二叉树节点,`buildTree`函数用于根据后缀表达式构造二叉树,`postorderTraversal`函数用于对二叉树进行后序遍历,`evaluateTree`函数用于计算二叉树的值,`infixToPostfix`函数用于将中缀表达式转换为后缀表达式。最后,我们可以通过输入中缀表达式来使用这些函数计算出表达式的值,并输出后缀表达式、二叉树后序遍历和表达式的值。
阅读全文