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

function eval(node)
eval(node->left)
eval(node->right)
if(node is a leaf node) push it on the stack
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;
        }

}

What exactly didn't work? Please show the relevant code and describe precisely what didn't work. — Björn Pollex
A recursive approach doesn't use a stack explicilty: it uses the stack of activation frames that you get automatically when you recurse. — user207421
To be honest I can't get your idea. First of all, why check the node is leaf after evaluate its sub-nodes? Should that be in reverse order? Second, is that node::value a field to store the evaluated value? if so what is the purpose of your stack? After all you already have the function call stack to use, and you don't need an explicit stack if you use recursion rather than loop. — Earth Engine
You don't need a tree to evaluate postfix. Possibly you are given an expression tree as input and are then required to convert it to postfix, or maybe you are required to evaluate it directly, which is also possible. Please clarify. Your question doesn't make sense. — user207421

SHR SHR · Accepted Answer · 2013-10-31T10:03:32

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

Evaluate Postfix expression using a tree in C++

2 Answers