使用 Python 构建和评估表达式树的程序
假设,我们得到了一个表达式树的后序遍历。我们需要根据给定的后序遍历构建一个表达式树,然后评估该表达式。我们返回表达式树的根节点以及树的计算结果。
因此,如果输入如下所示:
则输出将为 -7。
作为树输入给出的后缀表达式为 ['1', '2', '+', '3', '4', '+', '*']。如果对表达式进行计算,则变为 (1 – 2) * (3 + 4);结果等于 -7。
为了解决这个问题,我们将遵循以下步骤:
LEFT = 0 RIGHT = 1
定义一个函数 evaluate()。它将接收根节点作为参数。
如果根节点的值是数值,则
返回根节点值的整数表示形式。
left_val := evaluate(根节点的左子节点)
right_val := evaluate(根节点的右子节点)
如果根节点的值为 '+',则
返回 left_val + right_val
否则,当根节点的值为 '-' 时,则
返回 left_val - right_val
否则,当根节点的值为 '*' 时,则
返回 left_val * right_val
否则,当根节点的值为 '/' 时,则
返回 (left_val / right_val) 的向下取整值。
定义一个函数 buildTree()。它将接收后缀表达式作为参数。
root := null
stack := 一个新的列表
当后缀表达式不为空时,执行以下操作:
curr := 从后缀表达式中删除最后一个元素。
curr_node := 一个包含值 curr 的新节点。
如果 root 为空,则
root := curr_node
如果 stack 不为空,则
parent := 从 stack 中删除最后一个元素。
side := parent
如果 side 与 LEFT 相同,则
parent 的左子节点 := curr_node
否则,
parent 的右子节点 := curr_node
如果 curr 不是数值,则
在 stack 的末尾插入元组 (curr_node, LEFT)。
在 stack 的末尾插入元组 (curr_node, RIGHT)。
返回 root。
让我们看看下面的实现,以便更好地理解:
示例
LEFT = 0 RIGHT = 1 class Node(): def __init__(root, val, left = None, right = None): root.val = val root.left = left root.right = right def evaluate(root): if(root.val.isnumeric()): return int(root.val) left_val = evaluate(root.left) right_val = evaluate(root.right) return ( ( root.val == '+' and left_val + right_val ) or ( root.val == '-' and left_val - right_val ) or ( root.val == '*' and left_val * right_val ) or ( root.val == '/' and left_val // right_val ) ) def buildTree(postfix): root = None stack = [] while(postfix): curr = postfix.pop() curr_node = Node(curr) if(not root): root = curr_node if(stack): parent, side = stack.pop() if(side == LEFT): parent.left = curr_node else: parent.right = curr_node if(not curr.isnumeric()): stack.append((curr_node, LEFT)) stack.append((curr_node, RIGHT)) return root root = buildTree(['1', '2', '+', '3', '4', '+', '*']) print(evaluate(root))
输入
['1', '2', '+', '3', '4', '+', '*']
Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.
输出
-7