使用 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

更新于: 2021年5月28日

2K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告