c++ - 二叉表达式树评估

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 对象永远不会被删除。