python真值表表达式树生成打印
时间: 2023-07-25 17:23:31 浏览: 51
生成表达式树可以使用栈和递归的方法,具体步骤如下:
1. 遍历表达式,将操作数和操作符分别压入栈中。
2. 当遇到操作符时,弹出栈顶的两个操作数,作为当前操作符的左右子节点,创建一个新的节点,并将其压入栈中。
3. 遍历完表达式后,栈中只剩下一个节点,即根节点,返回该节点即可。
以下是Python代码实现:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def build_expression_tree(expression):
stack = []
for char in expression:
if char == ' ':
continue
elif char.isdigit():
node = Node(int(char))
stack.append(node)
else:
right = stack.pop()
left = stack.pop()
node = Node(char)
node.left = left
node.right = right
stack.append(node)
return stack.pop()
def print_expression_tree(node, level=0):
if node is None:
return
print(' ' * level + str(node.value))
print_expression_tree(node.left, level+1)
print_expression_tree(node.right, level+1)
```
使用示例:
```python
expression = '1 and 0 or 1 xor 0'
root = build_expression_tree(expression)
print_expression_tree(root)
```
输出结果:
```
xor
or
and
1
0
1
0
```