二進制表示樹評估

Question

我想評估一個二進制表達式樹。這是我迄今爲止編寫的代碼。我在評估它時摧毀了樹的節點。但問題是，在遞歸期間，它會查找它沒有的數據，我想。它只是不斷返回0

void calc(bnode *&b) 
{ 
    bnode *c; 
    int m; 
    switch (b->data.ch) 
    { 
     case '+':m=b->lchild->data.in+b->rchild->data.in; 
       break; 
     case '-':m=b->rchild->data.in-b->lchild->data.in; 
       break; 
     case '*':m=b->lchild->data.in*b->rchild->data.in; 
       break; 
     case '/':m=b->lchild->data.in/b->rchild->data.in; 
       break; 
     case '%':m=b->lchild->data.in%b->rchild->data.in; 
       break; 
    } 

    c=new(bnode); 
    c->lchild=NULL; 
    c->rchild=NULL; 
    c->tag=1; 
    c->data.in=m; 
    b=c; 
} 

int eval(bnode *b) 
{ 
    if (b->tag==1) 
    return b->data.in; 
    else 
    { 
     if (b->lchild->tag==0) 
      eval(b->lchild); 
     if (b->rchild->tag==0) 
      eval(b->rchild); 
     if (b->lchild->tag==1&&b->rchild->tag==1) 
      calc(b); 
    } 
} 

我所用的結構是

union un 
{ 
    int in; 
    char ch; 
}; 

struct bnode{ 
    bnode *lchild; 
    un data; 
    int tag; 
    bnode *rchild; 
}; 

Answer 1

功能eval()壞了。在「else」分支中，你永遠不會返回任何值，這是未定義的行爲。

[編輯] eval函數應該改成這樣。

int eval(bnode *b) 
{ 
    if (b->lchild && b->lchild->tag == 0) 
     eval(b->lchild); 
    if (b->rchild && b->rchild->tag == 0) 
     eval(b->rchild); 
    if (b->lchild && b->rchild && b->lchild->tag == 1 && b->rchild->tag == 1) 
     calc(b); 

    if (b->tag == 1) 
     return b->data.in; 
    else 
     throw "Evaluation error"; 
} 

您也有內存泄漏，因爲bnode對象從不刪除。