使用C语言中的树计算Postfix表达式

Question

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

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

我首先需要计算b子树并将其结果存储在节点中，然后是c*d，依此类推，直到我将结果存储在根节点中。

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

1. 函数评估（节点）
2. 评估（节点-

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

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

你有2个选择：

叶的评估：

1-只需将值推送到堆栈

评估非叶片：

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

Answer 2

您忘记了obj2。推动（温度）-

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