Expression Tree Evaluating Error [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question appears to be off-topic because it lacks sufficient information to diagnose the problem. Describe your problem in more detail or include a minimal example in the question itself.

Closed 9 years ago.

Improve this question

This is an expression tree that I had to make for a class but the evaluate function does not display anything when called. Any idea on where I went wrong or what I could be missing? From what we learned in class it looks like it should run.

#include <iostream>
#include <string>
using namespace std;


class TreeNode                              //Leaf Node
{
public:
    TreeNode(char key, int data, TreeNode* p)   //constructor
    {
                this->key = key;
                this->data = data;
                n = 1;
                left = NULL;
                right = NULL;
                parent = p;
    }


        TreeNode * left;
        TreeNode * right;
        TreeNode * parent;
        char key;
        int data;
        int n;

};
class ExpressionTree                //expression tree
{
public:

    void create();                  //creates binary expression tree
    TreeNode * root;                //instance of TreeNode
    int Evaluate(TreeNode * n);     //evaluates tree
    void InOrder(TreeNode * n);     //traverses tree InOrder
    void PreOrder(TreeNode *n);     //traverses tree PreOrder
    void PostOrder(TreeNode *n);    //traverses tree PostOrder
};

void ExpressionTree::create()       //creates binary expression tree
{
    root = new TreeNode('*',3,0 );
    root->left = new TreeNode('+',5,root);
    root ->left->left = new TreeNode('2',2,root->left);
    root ->left->right = new TreeNode('3',3,root->left);
    root->right = new TreeNode('5',5,root);

}
int ExpressionTree::Evaluate(TreeNode *n) //Evaluates tree
{

    int answer = 0;
    switch(n->key)                       //switch statement to decide what operator is being used
            {
                case '+':
                    answer = (Evaluate(n->left)+ Evaluate(n->right));
                    break;
                case '-':
                    answer = (Evaluate(n->left)- Evaluate(n->right));
                    break;
                case '*':
                    answer = (Evaluate(n->left)* Evaluate(n->right));
                    break;
                case '/':
                    answer = (Evaluate(n->left)/ Evaluate(n->right));
                    break;
            }
        return answer;                  //returns answer

}
void ExpressionTree::InOrder(TreeNode * n)  //traverses the tree InOrder
{
    if ( n ) {
           InOrder(n->left);
           cout << n->key << " ";
           InOrder(n->right);
        }
}
void ExpressionTree::PreOrder(TreeNode * n) //traverses the tree PreOrder
{
    if ( n ) {
           cout << n->key << " ";
           PreOrder(n->left);
           PreOrder(n->right);
        }
}
void ExpressionTree::PostOrder(TreeNode * n)//traverses the tree PostOrder
{
    if ( n ) {
           PostOrder(n->left);
           PostOrder(n->right);
           cout << n->key << " ";
        }
}

int main()                                  //main program
{
ExpressionTree * mytree;                    //creates instance of ExpressionTree
mytree->create();
cout<<"The Answer is: "<<endl;
mytree->Evaluate(mytree->root);
cout<<endl;
cout<<"In InOrder"<<endl;
mytree->InOrder(mytree->root);
cout<<endl;
cout<<"In PreOrder"<<endl;
mytree->PreOrder(mytree->root);
cout<<endl;
cout<<"In PostOrder"<<endl;
mytree->PostOrder(mytree->root);
cout<<endl;
}

Answer 1

• You failed to instantiate the ExpressionTree before use

  ExpressionTree* mytree = new ExpressionTree(); // THIS!
  mytree->create();
  

• You failed to print the value of the evaluation

  cout<<"The Answer is: "<<endl;
  cout << mytree->Evaluate(mytree->root); // THIS!
  

• You failed to handle leaf-nodes in Evaluate

  int ExpressionTree::Evaluate(TreeNode *n) { //Evaluates tree
  
      switch(n->operation) { //switch statement to decide what operator is being used
          case '+': return (Evaluate(n->left) + Evaluate(n->right));
          case '-': return (Evaluate(n->left) - Evaluate(n->right));
          case '*': return (Evaluate(n->left) * Evaluate(n->right));
          case '/': return (Evaluate(n->left) / Evaluate(n->right));
      }
      return n->data; // THIS!
  }
  

Now you're just left with a lot of memory management hell, and a pretty useless tree representation (unless you implement, e.g. a parser that returns one).

Also, there are many error-prone invariants on the TreeNode element, Evaluate chould be a virtual member of treenode and you chould have nullary, unary and binary expression tree nodes (nullary representing the values then).

Here's a version with the memory-management mishaps removed (exception safety left as an exercise): Live On Coliru

#include <iostream>
#include <string>
using namespace std;


class TreeNode {                            //Leaf Node
    TreeNode(TreeNode const&);            // no copy
    TreeNode& operator=(TreeNode const&); // no copy

public:
    TreeNode(char operation, int data, TreeNode* p)
      : left(0), right(0), parent(p),
        operation(operation), data(data)
    { //constructor
    }

    ~TreeNode() {
        delete left;
        delete right;
        left = right = 0;
    }

    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    char operation;
    int data;
};

class ExpressionTree {              //expression tree
    ExpressionTree(ExpressionTree const&);            // no copy
    ExpressionTree& operator=(ExpressionTree const&); // no copy
public:
    ExpressionTree() : root(0) {}

    void create();                  //creates binary expression tree
    TreeNode* root;                //instance of TreeNode
    int Evaluate(TreeNode * n);     //evaluates tree
    void InOrder(TreeNode * n);     //traverses tree InOrder
    void PreOrder(TreeNode *n);     //traverses tree PreOrder
    void PostOrder(TreeNode *n);    //traverses tree PostOrder

    ~ExpressionTree()
    {
        delete root;
        root = 0;
    }
};

void ExpressionTree::create() {     //creates binary expression tree
    root              = new TreeNode('*', 3, 0);
    root->left        = new TreeNode('+', 5, root);
    root->left->left  = new TreeNode('2', 2, root->left);
    root->left->right = new TreeNode('3', 3, root->left);
    root->right       = new TreeNode('5', 5, root);
}

int ExpressionTree::Evaluate(TreeNode *n) { //Evaluates tree

    switch(n->operation) { //switch statement to decide what operator is being used
        case '+': return (Evaluate(n->left) + Evaluate(n->right));
        case '-': return (Evaluate(n->left) - Evaluate(n->right));
        case '*': return (Evaluate(n->left) * Evaluate(n->right));
        case '/': return (Evaluate(n->left) / Evaluate(n->right));
    }
    return n->data;
}

void ExpressionTree::InOrder(TreeNode * n) { //traverses the tree InOrder
    if(n) {
        InOrder(n->left);
        cout << n->operation << " ";
        InOrder(n->right);
    }
}

void ExpressionTree::PreOrder(TreeNode * n) { //traverses the tree PreOrder
    if(n) {
        cout << n->operation << " ";
        PreOrder(n->left);
        PreOrder(n->right);
    }
}

void ExpressionTree::PostOrder(TreeNode * n) { //traverses the tree PostOrder
    if(n) {
        PostOrder(n->left);
        PostOrder(n->right);
        cout << n->operation << " ";
    }
}

int main() {                                //main program
    ExpressionTree* mytree = new ExpressionTree();
    mytree->create();
    cout<<"The Answer is: "<<endl;
    cout << mytree->Evaluate(mytree->root);
    cout<<endl;
    cout<<"In InOrder"<<endl;
    mytree->InOrder(mytree->root);
    cout<<endl;
    cout<<"In PreOrder"<<endl;
    mytree->PreOrder(mytree->root);
    cout<<endl;
    cout<<"In PostOrder"<<endl;
    mytree->PostOrder(mytree->root);
    cout<<endl;

    delete mytree;
}