计算表达式树 - C++

Question

我在使用没有指针作为参数的求值函数时遇到了一些问题。

class 定义如下：

class ExpressionTree
    {
    private:
        double data;            // Used for leaf nodes only.
        char operation;         // Used for non-leaf nodes only.
        ExpressionTree *left;   // Will be NULL for a leaf.
        ExpressionTree *right;  // Will be NULL for a leaf.
    };

如您所见，只有表达式树的 left 和 right 子树的指针。

这是我对 evaluate() 函数的尝试（注意没有指针作为参数传递）

double ExpressionTree::evaluate() const {
    if(left != NULL && right != NULL) {
        double val;

        double left_val = left->data;
        double right_val = right->data;

        if(operation == '+') val = left->evaluate() + right->evaluate();
        else if(operation == '*') val = left->evaluate() + right->evaluate();
        else val = this->data;
        return val;
    }
    else {
        return data;
    }
}

当运行它针对此代码时，我得到一个分段错误：

ExpressionTree buildComplex() {
    double x, y, z;
    cout << "enter three double values, x, then y, then z\n";
    cin >> x >> y >> z;
    ExpressionTree ex(x), ey(y), ez(z), e2(2),
        yz = ey * ez,
        y2 = e2 * ey,
        sum1 = ex + yz,
        full = sum1 + y2;
    return full;
}

void test4() {
    cout << "test4: construct and evaluate more complex\n";
    ExpressionTree e = buildComplex();
    cout << "x + y * z + 2 * y = " << e.evaluate() << endl;
}

我认为分段错误来自 evaluate() 函数中的递归调用。

我要问的问题是：如何在不将节点作为参数传递给函数的情况下递归评估树？如果根节点下面只有一层我能理解，但是会有多层，我不明白如何解决所有其他层。

谢谢！

Answer 1

您在同一个节点上调用 evaluate，创建了一个无限循环。

如果你想在子表达式上调用它，使用left->evaluate()。

可能还有更多问题，我注意到的是这个：

else if(right != NULL)

这没有意义，只是因为 left 不是 NULL 你要忽略正确的子表达式吗？

Answer 2

你的evaluate()方法是胡说八道。它应该看起来像这样：

double ExpressionTree::evaluate() const
{
    if (left != NULL && right != NULL)
    {
        switch (operation)
        {
        case '+':
            return left->evaluate()+right->evaluate();
        case '-':
            // remaining operators left as an exercise for the reader
        // ....
        }
    }
    // I'm assuming there are only binary operators,
    // but if you have unary operators, i.e. unary '-', it's a simple
    // extension of what's here
    return data;
}

计算表达式树 - C++

Evaluating expression tree - C++

c++

tree