Evaluate Postfix expression using a tree in C++

Question

I am supposed to evaluate a postfix expression using an expression tree. Suppose I have a tree like this

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

I first need to evaluate a+b subtree and store its result in the + node, then c*d and so on untill i have the result in root node.

I tried the recursive approach using a stack, but that wasn't working. The pseudocode looked like this

1. function eval(node)
2. eval(node->left)
3. eval(node->right)
4. if(node is a leaf node) push it on the stack
5. else if(node is an operand) pop a and pop b from stack node->value = a->value op b->value delete a b;

However this didn't work. I also have to show the tree on every step so as to show the nodes being reduced. I googled it many times but i was not able to find the required answer. Anyone please help me how to do this.

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

you have 2 options:

eval of leaf :

1 - just push value to stack

eval of non_leaf:

1 - eval left, - REMEMBER: the eval result added to stack.

2 - eval right,

3 - pop 2 items,

4 - calculate,

5 - push result.

at the end you'll have 1 item in the stack - the last result

EDIT:

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