表达式树数据结构

Question

我希望您能在C++中实现一个简单的算术表达式树数据结构，使得一个表达式树对象可以通过以下方式进行初始化：ExprTree(operator, expression1, expression2)。以下是它应该如何工作的示例：

double x = 1, y = 2, z = 0.5;
expr1 = ExprTree('*', x, y); // expr1 = 1 * 2 = 2
expr2 = ExprTree('-', expr1, z); // expr2 = (1 * 2) - 0.5 = 1.5
cout << expr2.str() << endl; // ((1 * 2) - 0.5)
cout << expr2.eval() << endl; // 1.5

这是目前我的代码的样子：

template<class operand_type>
class ExprTree
{
public:
    ExprTree(const char op_, operand_type& operand1_, operand_type& operand2_)
    {
        op = op_;
        operand1 = operand1_;
        operand2 = operand2_;
    }
    double eval() const;
    std::string str() const;
private:
    char op;
    typename operand_type operand1, operand2;
};

template<class operand_type>
std::string ExprTree<operand_type>::str() const
{
    std::ostringstream os;
    std::string op1, op2;
    if (typeid(*operand1) == typeid(ExprTree))
        op1 = operand1->str();
    else
        op1 = std::string(*operand1);
    if (typeid(*operand2) == typeid(ExprTree))
        op2 = operand1->str();
    else
        op2 = std::string(*operand2);
    os << "(" << op1 << " " << op << " " << op2 << ")";
    return os.str();
}

然而，当我编译代码时，会出现以下错误：

left of '->write' must point to class/struct/union/generic type

希望有人能够帮助我解决这个错误，并提供一些关于如何实现这个数据结构的技巧。顺便说一句，我对c ++非常陌生。

- Randolph

---

我没有看到相关的代码片段（调用write或者它的定义）。 - Unimportant

我已经编辑了代码。它应该读作“str”，而不是“write”。 - Randolph

在实例化对象时，需要添加模板类型：ExprTree<double> expr1('*', x, y); 下一行 ExprTree('-', expr1, z) 需要一个可以接受两个不同类型操作数的构造函数。 - Unimportant

注意：if (typeid(*operand1) == typeid(ExprTree))非常糟糕。你应该使用虚函数。 - Martin York

Answer 1

当你说：

operand1->str();

你应该说成：

operand1.str();

因为operand1不是指针，而是成员变量。

错误信息：

左侧的“->str”必须指向类/结构体/联合/通用类型

基本上是说运算符->的左侧必须是一个指针（它不是）。 （它还表示它必须指向类似的类，而不是例如整数）。

- rodrigo

Answer 2

您的代码存在以下问题：

1. 您在成员变量operand1和operand2上使用了指针成员运算符->

2. 您需要在模板参数中使用不同的类型来初始化具有不同参数类型的对象。

3. 类/构造函数不能像函数一样自动检测类型。这意味着您不能像这样做：ExprTree('*', x, y);。您必须指定模板参数或使用其他模板函数来构造ExprTree模板类的对象。请参见此答案。

4. if (typeid(*operand1) == typeid(ExprTree))会在运行时评估，因此您将收到编译错误，因为您尝试调用方法str()并将同一对象传递给std::string

我更喜欢以下解决方案：

#include <string>
#include <iostream>
#include <sstream>

template<typename operand_type_A, typename operand_type_B>
class ExprTree 
{
public:
    ExprTree(){};
    ExprTree(const char op_, const operand_type_A& operand1_, const operand_type_B& operand2_) {
        op = op_;
        operand1 = operand1_;
        operand2 = operand2_;
    };
    double eval() const;
    std::string str() const;

private:
    char op;
    operand_type_A operand1;
    operand_type_B operand2;
};

template<typename operand_type_A, typename operand_type_B>
ExprTree<operand_type_A, operand_type_B> makeExpr(const char op, const operand_type_A& operand1, const operand_type_B& operand2)
{
    return ExprTree<operand_type_A, operand_type_B>(op, operand1, operand2);
}

template<typename T>
std::string ToString(const T& x)
{
    return x.str();
}

template<>
std::string ToString<double>(const double& x)
{
    return std::to_string(x);
}

template<typename operand_type_A, typename operand_type_B>
std::string ExprTree<operand_type_A, operand_type_B>::str() const {
    std::ostringstream os;
    std::string op1, op2;
    op1 = ToString(operand1);
    op2 = ToString(operand2);
    os << "(" << op1 << " " << op << " " << op2 << ")";
    return os.str();
}

int main()
{
    double x = 1, y = 2, z = 0.5;
    std::cout << makeExpr('-', makeExpr('*', x, y), z).str() << std::endl;
    return 0;
}

它输出以下字符串：

((1.000000 * 2.000000) - 0.500000)

你可以在这里尝试。

- Pidhorskyi