Оцените выражение Postfix, используя дерево в C++

Question

Я должен оценивать постфиксное выражение, используя дерево выражений. Предположим, у меня есть такое дерево

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

Сначала мне нужно оценить поддерево + b и сохранить его результат в узле +, затем c * d и так далее, пока я не получу результат в корневом узле.

Я попробовал рекурсивный подход с использованием стека, но это не сработало. Псевдокод выглядел так

1. функция eval(узел)
2. Eval(node-> слева)
3. Eval(node-> справа)
4. если (узел является листовым узлом) поместите его в стек
5. иначе, если (узел является операндом), вытолкнуть a и pop b из стека node->value = a->value op b->value delete a 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

У вас есть 2 варианта:

Эваль листа:

1 - просто подтолкнуть значение в стек

Eval of non_leaf:

1 - eval left, - REMEMBER: результат eval добавляется в стек.

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.push(temp->balue); в остальной части

Однако ошибок больше, стек должен быть распределен между вызовами функций, чтобы функция могла его обработать.