使用Python构建和评估表达式树的程序

假设我们已经给出了表达式树的后序遍历。我们需要从给定的后序遍历构建表达式树，然后评估表达式。我们将返回表达式树的根和树的评估值。

因此，如果输入如下图所示：

那么输出将是-7。

给定树的后缀顺序为[‘1’，’2’，’+’，’3’，’4’，’+’，’‘]。如果计算表达式，则为（1-2）（3 + 4），结果为-7。

为了解决这个问题，我们将遵循以下步骤−

左= 0 右= 1
定义evaluate（）函数。这将采取根
- 如果根的值是数字值，则
  - 返回根值的整数表示形式
- left_val：= evaluate（根左侧）
- right_val：= evaluate（根的右侧）
- 如果根的值= ‘+’，则
  - 返回left_val + right_val
- 否则，当根的值= ‘-‘时，则
  - 返回left_val – right_val
- 否则，当根的值= ‘*’时，则
  - 返回left_val * right_val
- 否则，当根的值为’/’时，则
  - 返回左侧/右侧的floor值
定义buildTree（）函数。这将采取后缀
- 根：= null
- 堆栈：=一个新列表
- 当后缀不为空时，执行
  - 当前：=从后缀中删除最后一个元素
  - curr_node：=包含值curr的新节点
  - 如果根为空，则
  - 根：= curr_node
  - 如果堆栈不为空，则
  - parent：=从堆栈中删除最后一个元素
  - side：=父级
  - 如果侧与LEFT相同，则
    - 父级左侧：= curr_node
  - 否则，
    - 父级的右侧：= curr_node
  - 如果curr不是数字值，则
  - 在堆栈末尾插入元组（curr_node，LEFT）
  - 在堆栈末尾插入tuple（curr_node，RIGHT）
返回根

让我们看看以下实现，以获得更好的理解−

例子

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))