Expression tree data structure

Question

I want to implement a simple arithmetic expression tree data structure in c++, such that an expression tree object is initialised by: ExprTree(operator, expression1, expression2). Here is an example of how it should work:

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

Here is how my code looks so far:

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();
}

However, I get this error when I compile the code:

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

I would appreciate it if someone would help me with this error and possibly provide some tips as to how I should implement this data structure. Btw, I'm very new to c++.

Answer 1

There are a number of problems in your code:

1. You use member of pointer -> operator on member variables operand1 and operand2

2. You need two different types in template arguments to initialize object with different argument types.

3. Classes/constructors don't autodetect types like functions do. It means that you can not do a thing like ExprTree('*', x, y);. You have ether specify template arguments or use an additional template function to construct the object of ExprTree template class. See this answer.

4. The if (typeid(*operand1) == typeid(ExprTree)) evaluates at runtime, so you will get a compilation error because you try to call the method str() and pass the same object to std::string

I would prefer the following solution:

#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;
}

It outputs the following string:

((1.000000 * 2.000000) - 0.500000)

You may try it here.

Answer 2

When you say:

operand1->str();

You should say instead:

operand1.str();

Because operand1 is not a pointer but a member variable.

The error message

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

basically says that the left of operator -> must be a pointer (it is not). (It also say that it must point to a class or similar, not to an integer, for example).