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