2
\$\begingroup\$

There are many ways to implement a math expressions evaluator (I focus here just on the evaluator part, without any parsing).

I want to explore a certain implementation to support the following main:

int main() {
    Expression e = Sum( Sum(Number(2), Number(3)), Number(-1) );
    cout << e << "=" << e.eval() << endl;
}

The expected output is:

((2+3)+-1)=4

A basic notion: there are some temporary objects created there. We should better move them. So I came up with the following code I would like to consult about.


BaseExpression - an abstract base for all expressions

class BaseExpression {
public:
    virtual ~BaseExpression() {}
    // what do you think about the concept of the method 'get_unique_copy()' below?
    virtual std::unique_ptr<BaseExpression> get_unique_copy() && = 0;
    virtual double eval()const = 0;
    virtual void print(ostream& out)const = 0;
};

Expression - the actual non-abstract to hold an expression

class Expression {
    std::unique_ptr<BaseExpression> _e;
public:
    Expression(nullptr_t) {}
    Expression(BaseExpression&& e) 
    : _e(std::move(e).get_unique_copy()) {}
    ~Expression() {}
    Expression(Expression&& e) noexcept : _e(std::move(e._e)) {}
    Expression& operator=(Expression&& e) noexcept { std::swap(_e, e._e); return *this; }
    double eval() const { return _e->eval(); }
    friend ostream& operator<<(ostream& out, const Expression& e) {
        e._e->print(out);
        return out;
    }
};

Sum - an example of an actual expression

class Sum: public BaseExpression {
    Expression _e1{nullptr}, _e2{nullptr};
public:
    Sum(BaseExpression&& e1, BaseExpression&& e2) 
        : _e1(std::move(e1)), _e2(std::move(e2)) {}
    Sum(const Sum& s) = delete;
    Sum& operator=(const Sum& s) = delete;
    Sum(Sum&& s) noexcept {
        std::swap(_e1, s._e1);
        std::swap(_e2, s._e2);
    }
    // what do you think about the implementation of 'get_unique_copy()' below? is it safe?
    virtual std::unique_ptr<BaseExpression> get_unique_copy() && {
        return std::make_unique<Sum>(std::move(*this));
    }
    virtual double eval()const override {
        return _e1.eval() + _e2.eval();
    }
    virtual void print(ostream& out)const override {
        out << '(' << _e1 << '+' << _e2 << ')';
    }
};

Number - the simplest actual expression

class Number: public BaseExpression {
    double _d;
public:
    Number(double d) : _d(d) {}
    // what do you think about the duplication of 'get_unique_copy()' in each derived?
    // is there a way to avoid the duplication, apart from ugly Macros?
    virtual std::unique_ptr<BaseExpression> get_unique_copy() && {
        return std::make_unique<Number>(std::move(*this));
    }
    virtual double eval()const override {
        return _d;
    }
    virtual void print(ostream& out)const override {
        out << _d;
    }
};

What do you think?

http://coliru.stacked-crooked.com/a/9843afbe4e9ed4d8

\$\endgroup\$
4
\$\begingroup\$

I had a bunch of sections detailing the various aspects of your design that could be improved, but I ended up scrapping most of it, because at the end of the day, it can be resumed in two specific things:

But first: The idea of forcing RValues here is severely misguided. Forcing RValue usage should be limited to cases where things would break otherwise, not to enforce coding practices. What if someone wants to create a complex sub-expression and reuse it a few times? Tough luck!

1. Expression as a wrapper is misguided.

I do not like wrappers that exist just for the sake of giving value semantics to something. Value vs reference semantics should be delegated to the user as much as humanly possible as long as type erasure is not invovled. Specifically, someone will inevitably write std::unique_ptr<Expression> at some point in the future.

2. This is unjustifiably complicated.

You can obtain the same functionallity with bog-standard code, no need to get fancy. The trick is to separate the Sum() function in the API from the Sum type in the implementation.

class Expression {
public:
  virtual ~Expression() {};
  virtual std::unique_ptr<Expression> clone() const = 0;
};

class SumExpr : public Expression {
  std::unique_ptr<Expression> e1_;
  std::unique_ptr<Expression> e2_;
public:
  SumExpr(std::unique_ptr<Expression> e1, 
          std::unique_ptr<Expression> e2)
    : e1_(std::move(e1))
    , e1_(std::move(e2)) {}

  std::unique_ptr<Expression> clone() override {
    return std::make_unique<SumExpr>(e1->clone(), e2->clone());
  }
};

std::unique_ptr<Sum> Sum(std::unique_ptr<Expression> e1,
                         std::unique_ptr<Expression> e2) {
  return std::make_unique<SumExpr>(std::move(e1), std::move(e2));
}

Note that is is not "quite" how I'd go about implementing this, but this way matches your current functionality.

Bonus: Implement printing to ostream as operator <<

It's a shame that operator<<(std::ostream&, Sum const&) is not implemented. print() should delegate to it ideally, so that stream << Sum()...; can work

Now, at first glance, it would seem that this would require some really annoying boilerplate, but you can get around that using some crafty CRTP:

class Expression {
public:
  virtual std::ostream& print(std::ostream&) const = 0;
};

template<typename CRTP_T>
class ExpressionImpl : public Expression {
  std::ostream& print(std::ostream& stream) const override {
    return stream << *static_cast<CRTP_T const*>(this);
  }
};

class Sum : public ExpressionImpl<Sum> {
  friend std::ostream& operator<<(std::ostream&, Sum const&) {
    ...
  }
};

As an exercise to the reader, you can similarly create a BinaryExpression<CRTP_T> to avoid having to reimplement the clone() function in every single leaf class.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the review. The CRTP idea is very good. Regarding the use of rvalue - this was kind of an exercise where the main was given. So the idea was to see how to use rvalues for creating the polymorphic expressions. The example can be extended to allow also lvalues. And there are of course dozens of other ways for managing the expressions. One of the questions was, whether in the given code, as is, it is safe to move from *this. I believe that in the given code it is, but wanted to get assurance for that. \$\endgroup\$ – Amir Kirsh Dec 24 '17 at 16:31
  • \$\begingroup\$ Frank, I added below a revised version based on your inputs, I would be happy to get feedback on it, thanks! \$\endgroup\$ – Amir Kirsh Dec 24 '17 at 17:57
1
\$\begingroup\$

Based on the inputs from @Frank, suggesting the following code.

Please assume that the idea to "mandate" the use of temporary objects in the main is given. Now we wish to use these rvalues the best we can.

Based on the inputs we now allow creating an Expression based on a previous Expression. Here is the new main:

int main() {
    Expression e1 = Sum(Sum(Number(2), Number(3)), Number(-1));
    cout << e1 << "=" << e1.eval() << endl;
    Expression e2 = Exp(e1, Number(2));
    cout << e2 << "=" << e2.eval() << endl;
}

The expected output is:

((2+3)+-1)=4
(((2+3)+-1)^2)=16

AbstractBaseExpression - an abstract base for all expressions

class AbstractBaseExpression {
public:
    virtual ~AbstractBaseExpression() {}
    virtual std::unique_ptr<AbstractBaseExpression> get_unique_copy() && = 0;
    virtual double eval()const = 0;
    virtual void print(ostream& out)const = 0;
};

BaseExpression - an abstract base for expressions with CRTP

template<class ActualExpression>
class BaseExpression: public AbstractBaseExpression {
public:
    virtual std::unique_ptr<AbstractBaseExpression> get_unique_copy() && override {
        return std::make_unique<ActualExpression>
          (std::move(static_cast<ActualExpression&&>(*this)));
    }
};

Expression - the actual non-abstract to hold an expression

class Expression {
    std::shared_ptr<AbstractBaseExpression> _e;
public:
    Expression(AbstractBaseExpression&& e) 
    : _e(std::move(e).get_unique_copy()) {}
    double eval() const { return _e->eval(); }
    friend ostream& operator<<(ostream& out, const Expression& e) {
        e._e->print(out);
        return out;
    }
};

BinaryExpression - the base for all binary expressions

template<class ActualExpression, char sign>
class BinaryExpression: public BaseExpression<ActualExpression> {
    Expression _e1, _e2;
public:
    BinaryExpression(Expression e1, Expression e2)
    : _e1(std::move(e1)), _e2(std::move(e2)) {}
    virtual double evalImpl(double d1, double d2)const = 0;
    virtual double eval()const {
        return evalImpl(_e1.eval(), _e2.eval());
    }
    virtual void print(ostream& out)const override {
        out << '(' << _e1 << sign << _e2 << ')';
    }
};

Sum - an example of an actual expression

class Sum: public BinaryExpression<Sum, '+'> {
public:
    Sum(Expression e1, Expression e2): BinaryExpression(std::move(e1), std::move(e2)) {}
    virtual double evalImpl(double d1, double d2)const override {
        return d1 + d2;
    }
};

Exp - an example of another actual expression

class Exp: public BinaryExpression<Exp, '^'> {
public:
    Exp(Expression e1, Expression e2): BinaryExpression(std::move(e1), std::move(e2)) {}
    virtual double evalImpl(double d1, double d2)const override {
        return std::pow(d1, d2);
    }
};

Number - the simplest actual expression

class Number: public BaseExpression<Number> {
    double _d;
public:
    Number(double d) : _d(d) {}
    virtual double eval()const override {
        return _d;
    }
    virtual void print(ostream& out)const override {
        out << _d;
    }
};

http://coliru.stacked-crooked.com/a/6c199eeeb4db34e6

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.