c++ - 在 C++ 中使用树计算 Postfix 表达式

Question

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

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

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

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

1. 函数评估(节点)
2. 评估(节点->左)
3. 评估(节点->右)
4. if(节点是叶节点)将其压入堆栈
5. else if(节点是一个操作数)从堆栈中弹出 a 和弹出 bnode->value = a->value op b->value删除一个b；

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

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); 在 else 部分

但是错误比较多，函数调用之间需要共享栈，函数才能真正处理