LINUX.ORG.RU

Сворачивание констант в дереве (constant folding).

 


0

2

Помогите разобраться с заданием:

В этой задаче вам необходимо реализовать сворачивание констант в дереве (constant folding). Например, у нас есть выражение (точнее, дерево, описывающее это выражение) abs(var * sqrt(32.0 - 16.0)), на выходе мы должны получить дерево для следующего выражения abs(var * 4.0), т. е. подвыражение sqrt(32.0 - 16.0) было вычислено.

Для того, чтобы определить, что выражение (Expression) на самом деле является числом (Number), используйте оператор dynamic_cast.

Все промежуточные узлы дерева, которые вы создали, нужно освободить.

#include <cassert>
#include <string>
#include <cmath>

struct Transformer;
struct Number;
struct BinaryOperation;
struct FunctionCall;
struct Variable;

struct Expression
{
    virtual ~Expression() { }
    virtual double evaluate() const = 0;
    virtual Expression *transform(Transformer *tr) const = 0;
};

struct Transformer
{
    virtual ~Transformer() { }
    virtual Expression *transformNumber(Number const *) = 0;
    virtual Expression *transformBinaryOperation(BinaryOperation const *) = 0;
    virtual Expression *transformFunctionCall(FunctionCall const *) = 0;
    virtual Expression *transformVariable(Variable const *) = 0;
};

struct Number : Expression
{
    Number(double value);
    double value() const;
    double evaluate() const;
    Expression *transform(Transformer *tr) const;

private:
    double value_;
};

struct BinaryOperation : Expression
{
    enum {
        PLUS = '+',
        MINUS = '-',
        DIV = '/',
        MUL = '*'
    };
    BinaryOperation(Expression const *left, int op, Expression const *right);
    ~BinaryOperation();
    double evaluate() const;
    Expression *transform(Transformer *tr) const;
    Expression const *left() const;
    Expression const *right() const;
    int operation() const;

private:
    Expression const *left_;
    Expression const *right_;
    int op_;
};

struct FunctionCall : Expression
{
    FunctionCall(std::string const &name, Expression const *arg);
    ~FunctionCall();
    double evaluate() const;
    Expression *transform(Transformer *tr) const;
    std::string const &name() const;
    Expression const *arg() const;

private:
    std::string const name_;
    Expression const *arg_;
};

struct Variable : Expression
{
    Variable(std::string const name);
    std::string const & name() const;
    double evaluate() const;
    Expression *transform(Transformer *tr) const;

private:
    std::string const name_;
};


/**
 * реализйте все необходимые методы
 * если считаете нужным, то можете
 * заводить любые вспомогетльные
 * методы
 */
struct FoldConstants : Transformer
{
    Expression *transformNumber(Number const *number)
    { }

    Expression *transformBinaryOperation(BinaryOperation const *binop)
    { }

    Expression *transformFunctionCall(FunctionCall const *fcall)
    { }

    Expression *transformVariable(Variable const *var)
    {  }
};

Вот мое решение, но оно не проходит тест:

struct FoldConstants : Transformer
{
    Expression *transformNumber(Number const *number)
    {
        return new Number(number->value());
    }
    Expression *transformBinaryOperation(BinaryOperation const *binop)
    {
        Expression * a;
        Expression * b;
        if (dynamic_cast<Number*>(binop->left()->transform(this)))
            {a = binop->left()->transform(this);}
        else
            {a = (Number*)(binop->left()->transform(this));}
        if (dynamic_cast<Number*>(binop->right()->transform(this)))
            {b = binop->right()->transform(this);}
        else
            {b = (Number*)(binop->right()->transform(this));}

        BinaryOperation * c = new BinaryOperation(a, binop->operation(), b);
        return new Number(c->evaluate());
        delete c;
    }
    Expression *transformFunctionCall(FunctionCall const *fcall)
    {
        Expression * a;
        if (dynamic_cast<Number*>(fcall->arg()->transform(this)))
            {a = fcall->arg()->transform(this);}
        else
            {a = (Number*)(fcall->arg()->transform(this));}
        FunctionCall * b = new FunctionCall(fcall->name(), a);
        return new Number(b->evaluate());
        delete b;
    }
    Expression *transformVariable(Variable const *var)
    {
        return new Variable(var->name());
    }
};

★★

Ответ на: комментарий от anonymous

Т.к. я только учусь и прохожу курс по С++, то меня интересует, верно ли мое «направление» решения этой задачи и в чем моя ошибка?

Pirr ★★ ()

Давай ты как-нибудь конкретизируешь, что тебе не ясно и где нужна помощь, а то читать всю это портянку кода как-то не очень интересно

Gvidon ★★★★ ()
Ответ на: комментарий от Gvidon

Вот ход моих мыслей например для BinaryOperation:

1. Создаю указатели на левое и правое выражение.

2. Проверяю является ли left и right экземплярами типа Number, и если не являются то привожу к типу Number.

3. Создаю новый экземпляр класса BinaryOperation;

4. Возвращаю новый экземпляр класса Number, проинициализировав его значением выражения.

5. Удаляю созданный экземпляр класса BinaryOperation чтобы не было утечек памяти.

Pirr ★★ ()

transformBinaryOperation - это что-то с чем-то возвращающее (точнее пытающееся вернуть) всегда число, а что тогда будет с var * 4 ?

io ★★ ()
Ответ на: комментарий от io

Вот полный код BinaryOperation:

struct BinaryOperation : Expression
{
    enum {
        PLUS = '+',
        MINUS = '-',
        DIV = '/',
        MUL = '*'
    };

    BinaryOperation(Expression const *left, int op, Expression const *right)
        : left_(left), op_(op), right_(right)
    { assert(left_ && right_); }

    ~BinaryOperation()
    {
        delete left_;
        delete right_;
    }

    Expression const *left() const
    { return left_; }

    Expression const *right() const
    { return right_; }

    int operation() const
    { return op_; }

    double evaluate() const
    {
        double left = left_->evaluate();
        double right = right_->evaluate();
        switch (op_)
        {
        case PLUS: return left + right;
        case MINUS: return left - right;
        case DIV: return left * right;
        case MUL: return left * right;
        }
        assert(0);
        return 0.0;
    }
    Expression *transform(Transformer *tr) const
    {
        return tr->transformBinaryOperation(this);
    }

private:
    Expression const *left_;
    Expression const *right_;
    int op_;
};
Pirr ★★ ()
Ответ на: комментарий от Pirr

«на выходе мы должны получить дерево для следующего выражения abs(var * 4.0)»

Как это возможно, если на выходе transformBinaryOperation мы всегда получаем число? Уже var * 4.0 будет превращено в число!

Про преобразования в число молчу.

io ★★ ()
Ответ на: комментарий от io

Всё возможно:

struct FoldConstants : Transformer
{
    Expression *transformNumber(Number const *number)
    {
        return new Number(number->value());
    }
    Expression *transformBinaryOperation(BinaryOperation const *binop)
    {
        Expression * left_new = (binop->left())->transform(this);
        Expression * right_new = (binop->right())->transform(this);
        if (dynamic_cast<Number*>(left_new) && dynamic_cast<Number*>(right_new))
        {
            Expression * a = new Number(binop->evaluate());
            delete left_new;
            delete right_new;
            return a;
        }
        else
        {
            Expression *b = new BinaryOperation((binop->left())->transform(this),
                                                binop->operation(),
                                                (binop->right())->transform(this));
            delete left_new;
            delete right_new;
            return b;
        }
    }
    Expression *transformFunctionCall(FunctionCall const *fcall)
    {
        Expression * a = (fcall->arg())->transform(this);
        if (dynamic_cast<Number*>(a))
        {
            Expression * b = new Number(fcall->evaluate());
            delete a;
            return b;
        }
        else
        {
            Expression * b = new FunctionCall(fcall->name(), (fcall->arg())->transform(this));
            delete a;
            return b;
        }
    }
    Expression *transformVariable(Variable const *var)
    {
        return new Variable(var->name());
    }
};
Pirr ★★ ()
Ответ на: комментарий от io

А, ну это я видел... это у препода опечатка была, как бы на суть задачи это не влияет. Спасибо, что уделили моему коду свое внимание.

Pirr ★★ ()
Ответ на: комментарий от Pirr

А каков резон выполнять каждый transform дважды?

Expression * left_new = (binop->left())->transform(this);
Expression *b = new BinaryOperation((binop->left())->transform(this),

io ★★ ()
Ответ на: комментарий от Pirr

Уважаемый, я прохожу тот же курс и застрял почти на том же этапе. Но вы, похоже, продвинулись дальше, чем я ;) Если это возможно и не затруднит, предлагаю связаться. Хотя дедлайн по данным трем задачам истекает сегодня, тем не менее, хочется до конца разобраться для себя. Напишите мне, пожалуйста, на адрес tusechka111@yandex.ru

Kopay ()

Коллега, так вы разобрались с этой проблемой? Вот мой код, но тоже WA

 #include <cassert>
#include <string>
#include <cmath>

struct Transformer;
struct Number;
struct BinaryOperation;
struct FunctionCall;
struct Variable;

struct Expression
{
    virtual ~Expression() { }
    virtual double evaluate() const = 0;
    virtual Expression *transform(Transformer *tr) const = 0;
        virtual Expression* clone() const = 0;
};

struct Transformer
{
    virtual ~Transformer() { }
    virtual Expression *transformNumber(Number const *) = 0;
    virtual Expression *transformBinaryOperation(BinaryOperation const *) = 0;
    virtual Expression *transformFunctionCall(FunctionCall const *) = 0;
    virtual Expression *transformVariable(Variable const *) = 0;
};

struct Number : Expression
{
    Number(double value);
    double value() const;
    double evaluate() const;
    Expression *transform(Transformer *tr) const;
    Expression* clone() const {
       return new Number(value_);
    }

private:
    double value_;
};

struct BinaryOperation : Expression
{
    enum {
        PLUS = '+',
        MINUS = '-',
        DIV = '/',
        MUL = '*'
    };
    BinaryOperation(Expression const *left, int op, Expression const *right);
    ~BinaryOperation();
    double evaluate() const;
    Expression *transform(Transformer *tr) const;
    Expression const *left() const;
    Expression const *right() const;
    int operation() const;
    
    Expression* clone() const {
        if(dynamic_cast<const Number*>(left_) && dynamic_cast<const Number*>(right_)){
             return new Number(evaluate());   
        }
        else return new BinaryOperation(left_->clone(), op_, right_->clone());
    }


private:
    Expression const *left_;
    Expression const *right_;
    int op_;
};

struct FunctionCall : Expression
{
    FunctionCall(std::string const &name, Expression const *arg);
    ~FunctionCall();
    double evaluate() const;
    Expression *transform(Transformer *tr) const;
    std::string const &name() const;
    Expression const *arg() const;
    Expression* clone() const {
        
        if(dynamic_cast<const Number*>(arg_)) 
            return new Number(this->evaluate());
        else return new FunctionCall(name_, arg_->clone());
        

    }

private:
    std::string const name_;
    Expression const *arg_;
};

struct Variable : Expression
{
    Variable(std::string const name);
    std::string const & name() const;
    double evaluate() const;
    Expression *transform(Transformer *tr) const;
    Expression* clone() const {
        Expression *ex = new Variable(name_);
        return ex;
    }

private:
    std::string const name_;
};


/**
 * реализуйте все необходимые методы
 * если считаете нужным, то можете
 * заводить любые вспомогательные
 * методы
 */
struct FoldConstants : Transformer
{
   Expression *transformNumber(Number const *number)
    {
        return number->clone();
    }

    Expression *transformBinaryOperation(BinaryOperation const *binop)
    {
        return binop->clone();
    }

    Expression *transformFunctionCall(FunctionCall const *fcall)
    {
        return fcall->clone();
    }

    Expression *transformVariable(Variable const *var)
    {
       return var->clone();
    }
};

mikemoix ()
Ответ на: комментарий от Pirr
        case DIV: return left * right;
        case MUL: return left * right;

top kek

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.