c++ - 在 C++ 中使用树评估 Postfix 表达式

Question

我应该使用表达式树来评估后缀表达式。假设我有一棵这样的树

    -
   / \
  +   *
 / \  / \
a  b  c  d

我首先需要评估 a+b 子树并将其结果存储在 + 节点中，然后 c*d 等等，直到我将结果存储在根节点中。

我尝试了使用堆栈的递归方法，但这不起作用。伪代码看起来像这样

1. 函数评估（节点）
2. 评估（节点->左）
3. 评估（节点->右）
4. if(node 是叶节点) 将其压入堆栈
5. else if(node is an operand) pop a and pop b from stack node->value = a->value op b->value delete ab;

然而这并没有奏效。我还必须在每一步都显示树，以显示正在减少的节点。我用谷歌搜索了很多次，但我找不到所需的答案。任何人都请帮助我如何做到这一点。

void expression_tree::evaluate(node *temp)
{
    if(!temp)
    return;
/// stack_postfix obj;
    stack_postfix obj2;
    evaluate(temp->left);
    evaluate(temp->right);
        if(temp->right == NULL && temp->left == NULL)
        {
            obj2.push(temp);
        }
        else
        {
            node * a = obj2.pop();
            node *b = obj2.pop();
            temp->value = a->value + b->value;
            delete a;
            delete b;
        }

}

Answer 1

你忘了obj2.push(temp->balue);在其他部分

但是错误比较多，函数调用之间需要共享栈，所以函数可以实际处理

Answer 2

你有两个选择：

叶的评估：

1 - 只是将值推入堆栈

non_leaf 的评估：

1 - 评估左， - 记住：评估结果添加到堆栈。

2 - 评估正确，

3 - 弹出 2 个项目，

4 - 计算，

5 - 推送结果。

最后，您将在堆栈中有 1 个项目 - 最后一个结果

编辑：

void expression_tree::evaluate(node *temp, stack& s)
{
   if(!temp)
      return;

   if(temp->left != NULL && temp->right  != NULL){
       //only 1 pointer is illegal!
       evaluate(temp->left);
       evaluate(temp->right);
       node* n2 = s.pop();
       node* n1 = s.pop();
       //in the stack should be only leaves
       temp->value = n1->value + n2->value;//use switch by operator 
       delete temp->left; 
       temp->left = NULL;
       delete temp->right; 
       temp->right=NULL;
   }
   s.push (temp);
}