表達式樹評估錯誤

Question

這是一個表達式樹，我必須爲一個類做出，但評估函數調用時不顯示任何東西。任何想法，我錯了什麼地方或我可能會失蹤？從我們在課堂上學到的東西看，它應該運行。

#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

• 你沒有使用之前實例化ExpressionTree

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

• 您打印失敗的評價值

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

• 您未能處理的葉節點在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! 
  } 
  

現在你只是留下了一個很大的內存管理地獄，一個很沒用的樹表示（除非你實現，例如一個解析器返回一個）。

而且，存在的TreeNode元件上許多容易出錯不變量，Evaluate chould是樹節點的虛擬構件和你chould有無參，一元和二元表達式樹節點（無參代表值即可）。

下面是在卸下內存管理事故的一個版本（異常安全作爲一個練習）：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; 
}