Einen benutzerdefinierten Ausdrucksbaum im Geist bauen: Qi (ohne Utree oder Boost :: Variante)

boost-spirit boost-spirit-qi c++ expression-trees parsing

Frage

Vor allem, wenn es mit Boost Variant oder Utree viel einfacher ist, dann werde ich mich mit ihnen abfinden, und ich werde versuchen, meine Probleme mit ihnen in einem anderen Thema zu lösen. Allerdings würde ich sehr gerne in der Lage sein, einen Baum zu bauen, wie ich unten habe.

Hintergrund, ignoriere, wenn du direkt auf das Thema eingehen möchtest: Ich möchte gerne einen Ausdrucksbaum bauen, der so etwas parst

"({a} == 0) && ({b} > 5)"

oder ein mathematischer Standardausdruck

"(2 * a) + b"

Ich werde dann definieren, was a und b sind, bevor ich meinen Baum auswerte, etwa so:

a = 10;
double val = myExpression->Evaluate();

Mein Problem tritt auf, wenn ich versuche, den String in meinen Ausdrucksbaum zu zerlegen. Ich verwende eine abstrakte Klasse "Expression", die dann "Variable", "Constant" und "Binary" -Ausdrücke ableitet (es wird auch unär, aber es sollte nicht mein Problem beeinflussen. Ich habe weiterhin Probleme mit dem Hinzufügen der Baum mit meinen Regeln , also mache ich eindeutig etwas falsches.Ich habe es schwer, meinen Kopf um die Attribute zu legen.

Mein Baum ist wie folgt (Tree.h):

class BinaryExpression;
typedef double (*func)(double, double);

class Expression
{
public:
    virtual double Evaluate() = 0;
};

class BinaryExpression : public Expression
{
private:
    Expression* lhs;
    Expression* rhs;
    func method;

    double Evaluate();

public:
    BinaryExpression(void);
    BinaryExpression(char op, Expression* lhs, Expression* rhs);
    BinaryExpression(char op);
    void operator()(Expression* lhs, Expression* rhs);
};

class ConstantExpression : public Expression
{
private:
    double value;
public:
    ConstantExpression(void);
    ConstantExpression(char op);
    ConstantExpression(double val);

    double Evaluate();
};

// Require as many types as there are fields in expression?
static double a;
static double b;
class VariableExpression : public Expression
{
private:
    char op;

public:
    VariableExpression(char op);

    double Evaluate();
};

BOOST_FUSION_ADAPT_STRUCT(
    BinaryExpression,
    (Expression*, lhs)
    (Expression*, rhs)
    (func, method)
)

BOOST_FUSION_ADAPT_STRUCT(
    VariableExpression,
    (char, op)
)

BOOST_FUSION_ADAPT_STRUCT(
    ConstantExpression,
    (double, op)
)

Baum.cpp

typedef double (*func)(double, double);

/////////////////////////////////////////////////////////////////////////////
// BINARY EXPRESSION
////////////////////////////////////////////////////////////////////////////

BinaryExpression::BinaryExpression(void) {}

BinaryExpression::BinaryExpression(char op, Expression* lhs, Expression* rhs)
{
    this->lhs = lhs;
    this->rhs = rhs;

    // Example, methods are held in another header
    if (op == '+')
        method = Add;
    else if (op == '-')
        method = Subtract;

}

double BinaryExpression::Evaluate()
{
    return method(lhs->Evaluate(), rhs->Evaluate());
}

BinaryExpression::BinaryExpression(char op)
{
    if (op == '+')
        method = Add;
    else if (op == '-')
        method = Subtract;
}

void BinaryExpression::operator()(Expression* lhs, Expression* rhs)
{
    this->lhs = lhs;
    this->rhs = rhs;
}

/////////////////////////////////////////////////////////////////////////////
// CONSTANT EXPRESSION
////////////////////////////////////////////////////////////////////////////

ConstantExpression::ConstantExpression() {}

ConstantExpression::ConstantExpression(char op)
{
    this->value = op - 48;
}
ConstantExpression::ConstantExpression(double val)
{
    value = val;
}

double ConstantExpression::Evaluate()
{
    return value;
}

/////////////////////////////////////////////////////////////////////////////
// VARIABLE EXPRESSION
////////////////////////////////////////////////////////////////////////////

VariableExpression::VariableExpression(char op)
{
    this->op = op;
}

double VariableExpression::Evaluate()
{
    // a and b are defined in the header, and are used to fill in the variables we     want to evaluate
    if (op == 'a')
        return a;
    if (op == 'b')
        return b;
    return 0;
}

Nun, wenn ich den Baum manuell erstelle alles funktioniert gut, so dass ich glaube nicht, es gibt ein Problem mit der Art, wie es strukturiert ist.

Hier ist Grammar.h (Viele Kommentare von wo ich verschiedene Dinge ausprobiert habe, ich könnte sie entfernen, aber ich kann es wert sein zu zeigen, was ich versucht habe / wo ich mit ihm gehen will)

#include "Tree.h"

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_function.hpp>

namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;

qi::_1_type _1;
qi::_2_type _2;

// Pass functions to boost
boost::phoenix::function<BinaryExpression> plus = BinaryExpression('+');
boost::phoenix::function<BinaryExpression> minus = BinaryExpression('-');

template <typename Iterator>
struct ExpressionParser : qi::grammar<Iterator, BinaryExpression(), ascii::space_type>
{
    ExpressionParser() : ExpressionParser::base_type(expression)
    {
        qi::_3_type _3;
        qi::_4_type _4;

        qi::char_type char_;
        qi::uint_type uint_;
        qi::_val_type _val;
        qi::raw_type raw;
        qi::lexeme_type lexeme;
        qi::alpha_type alpha;
        qi::alnum_type alnum;
        qi::bool_type bool_;
        qi::double_type double_;


        expression = //?
            additive_expr                       [_val = _1]
            ;

        //equality_expr = 
        //      relational_expr >> 
        //      *(lit("==") > relational_expr)      [/*Semantice action to add to tree*/]
        //      ;

        additive_expr =
            primary_expr >>
            ( '+' > primary_expr)               [plus(_val, _1)]   
            | ( '-' > primary_expr)             [minus(_val, _1)]
            ;
        // Also tried "_val = plus(_1, _2)"

        primary_expr =
            constant                                [_val = _1]
            | variable                          [_val = _1]
            //| '(' > expression > ')'          [_val = _1]
            ;

        string %=
            '{' >> *(char_ - '}') >> '}'
            ;

        // Returns ConstantExpression
        constant =
            double_                                 [_val = _1];

        // Returns VariableExpression
        variable =
            char_                                   [_val = _1]
            ;
    }

    // constant expression = double
    // variable expression = string
    qi::rule<Iterator, BinaryExpression(), ascii::space_type>
        expression;

    qi::rule<Iterator, BinaryExpression(), ascii::space_type>
        // eventually will deal with all these rules
        equality_expr,
        relational_expr,        
        logical_expr,
        additive_expr,
        multiplicative_expr,
        primary_expr
            ;

    qi::rule<Iterator, ConstantExpression(), ascii::space_type>
        constant
        ;

    qi::rule<Iterator, VariableExpression(), ascii::space_type>
        variable
        ;

    qi::rule<Iterator, std::string(), ascii::space_type>
        string
        ;
};

Also das ist ein wirklich abgehacktes, aber hoffentlich wird es zeigen, was ich versuche zu erreichen. Irgendwelche Ratschläge oder Tipps würden wirklich geschätzt werden. Gibt es ein Beispiel, wo jemand einen Baum wie diesen gebaut hat, ohne eine Variante oder einen Baum zu benutzen?

Es tut mir leid, wenn ich die Konvention gebrochen habe, und für meine Formatierung habe ich versucht, es so leserlich wie möglich zu machen.

Akzeptierte Antwort

Es ist mir nicht klar, was Sie mit (rekursiven) Varianten anstellen, aber hier ist eine Variation, die mit Ihrem Wunsch verbunden ist, 'altmodische' Baumbildung mit dynamisch zugewiesenen Knoten zu verwenden:

Ich habe das Problem der Vorrangstellung des Operators in Ihrer Grammatik bewusst umgangen, weil

Beachte wie ich

  • entfernte allgegenwärtige Speicherlecks mit shared_ptr (Sie können Boost verwenden , wenn Sie keine TR1-Bibliothek haben)
  • Ich entfernte die fehlgeleitete Wiederverwendung einer bestimmten BinaryExpression-Instanz als phoenix faulen Schauspieler . Stattdessen habe ich eine lokale makebinary jetzt Schauspieler.
  • Beachten Sie, wie Ketten von Operatoren (1 + 2 + 5 + 6-10) jetzt unterstützt werden:

    additive_expr =
        primary_expr                         [ _val = _1 ]
        >> *(char_("-+*/") >> primary_expr)  [ _val = makebinary(_1, _val, _2)]
        ;
    
  • Ich habe {var} , / , * und (expr) Unterstützung (expr)

  • hinzugefügt Serialisierung für die Anzeige ( Print virtuelle Methode, operator<< ) (für die Anzeige Bequemlichkeit speichert Binary den operator anstelle des resultierenden method jetzt)

  • Daher können Sie jetzt BOOST_SPIRIT_DEBUG verwenden (die erste Zeile auskommentieren)
  • Ich habe Expression in AbstractExpression (und de Konstruktor geschützt gemacht )
  • Ich habe PrimaryExpression in Expression (und dies ist nun der wichtigste Ausdruck-Datentyp )
  • Ich zeige, wie man vereinfachte Variablen in einer static Karte speichert
  • Verwendet weit weniger Fusions-Struktur-Anpassung (nur für variable jetzt)
  • Verwendet den Vorlagen-Konstrukttrick, um es sehr einfach zu machen, einen Ausdruck aus verschiedenen geparsten Typen zu erstellen:

    struct Expression : AbstractExpression {
        template <typename E>
        Expression(E const& e) : _e(make_from(e)) { } // cloning the expression
        // ...
    };
    

    ist genug um effizient zu unterstützen zB:

    primary_expr =
          ( '(' > expression > ')' )         [ _val = _1 ]
        | constant                           [ _val = _1 ]
        | variable                           [ _val = _1 ]
        ;
    
  • zum Spaß haben ein paar mehr Testfälle enthalten:

    Input:                3*8 + 6
    Expression:           Expression(BinaryExpression(BinaryExpression(ConstantExpression(3) * ConstantExpression(8)) + ConstantExpression(6)))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    30
    ----------------------------------------
    Input:                3*(8+6)
    Expression:           Expression(BinaryExpression(ConstantExpression(3) * BinaryExpression(ConstantExpression(8) + ConstantExpression(6))))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    42
    ----------------------------------------
    Input:                0x1b
    Expression:           Expression(ConstantExpression(27))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    27
    ----------------------------------------
    Input:                1/3
    Expression:           Expression(BinaryExpression(ConstantExpression(1) / ConstantExpression(3)))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    0.333333
    ----------------------------------------
    Input:                .3333 * 8e12
    Expression:           Expression(BinaryExpression(ConstantExpression(0.3333) * ConstantExpression(8e+12)))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    2.6664e+12
    ----------------------------------------
    Input:                (2 * a) + b
    Expression:           Expression(BinaryExpression(BinaryExpression(ConstantExpression(2) * VariableExpression('a')) + VariableExpression('b')))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               10, 7
    Evaluation result:    27
    ----------------------------------------
    Input:                (2 * a) + b
    Expression:           Expression(BinaryExpression(BinaryExpression(ConstantExpression(2) * VariableExpression('a')) + VariableExpression('b')))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               -10, 800
    Evaluation result:    780
    ----------------------------------------
    Input:                (2 * {a}) + b
    Expression:           Expression(BinaryExpression(BinaryExpression(ConstantExpression(2) * VariableExpression('a')) + VariableExpression('b')))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               -10, 800
    Evaluation result:    780
    ----------------------------------------
    Input:                {names with spaces}
    Expression:           Expression(VariableExpression('names with spaces'))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    0
    ----------------------------------------
    

Vollständiger Code

// #define BOOST_SPIRIT_DEBUG
// #define BOOST_RESULT_OF_USE_DECLTYPE
// #define BOOST_SPIRIT_USE_PHOENIX_V3

#include <cassert>
#include <memory>
#include <iostream>
#include <map>

struct AbstractExpression;
typedef std::shared_ptr<AbstractExpression> Ptr;

struct AbstractExpression {
    virtual ~AbstractExpression() {}
    virtual double Evaluate() const = 0;
    virtual std::ostream& Print(std::ostream& os) const = 0;

    friend std::ostream& operator<<(std::ostream& os, AbstractExpression const& e)
        { return e.Print(os); }

    protected: AbstractExpression() {}
};

template <typename Expr> // general purpose, static Expression cloner
    static Ptr make_from(Expr const& t) { return std::make_shared<Expr>(t); }

struct BinaryExpression : AbstractExpression 
{
    BinaryExpression() {}

    template<typename L, typename R>
    BinaryExpression(char op, L const& l, R const& r) 
        : _op(op), _lhs(make_from(l)), _rhs(make_from(r)) 
    {}

    double Evaluate() const {
        func f = Method(_op);
        assert(f && _lhs && _rhs);
        return f(_lhs->Evaluate(), _rhs->Evaluate());
    }

  private:
    char _op;
    Ptr _lhs, _rhs;

    typedef double(*func)(double, double);

    static double Add(double a, double b)      { return a+b; }
    static double Subtract(double a, double b) { return a-b; }
    static double Multuply(double a, double b) { return a*b; }
    static double Divide(double a, double b)   { return a/b; }

    static BinaryExpression::func Method(char op)
    {
        switch(op) {
            case '+': return Add;
            case '-': return Subtract;
            case '*': return Multuply;
            case '/': return Divide;
            default:  return nullptr;
        }
    }
    std::ostream& Print(std::ostream& os) const
        { return os << "BinaryExpression(" << *_lhs << " " << _op << " " << *_rhs << ")"; }
};

struct ConstantExpression : AbstractExpression {
    double value;
    ConstantExpression(double v = 0) : value(v) {}

    double Evaluate() const { return value; }

    virtual std::ostream& Print(std::ostream& os) const
        { return os << "ConstantExpression(" << value << ")"; }
};

struct VariableExpression : AbstractExpression {
    std::string _name;

    static double& get(std::string const& name) {
        static std::map<std::string, double> _symbols;
        return _symbols[name];
        /*switch(name) {
         *    case 'a': static double a; return a;
         *    case 'b': static double b; return b;
         *    default:  throw "undefined variable";
         *}
         */
    }

    double Evaluate() const { return get(_name); }

    virtual std::ostream& Print(std::ostream& os) const
        { return os << "VariableExpression('" << _name << "')"; }
};

struct Expression : AbstractExpression
{
    Expression() { }

    template <typename E>
    Expression(E const& e) : _e(make_from(e)) { } // cloning the expression

    double Evaluate() const { assert(_e); return _e->Evaluate(); }

    // special purpose overload to avoid unnecessary wrapping
    friend Ptr make_from(Expression const& t) { return t._e; }
  private:
    Ptr _e;
    virtual std::ostream& Print(std::ostream& os) const
        { return os << "Expression(" << *_e << ")"; }
};

//Tree.cpp

/////////////////////////////////////////////////////////////////////////////
// BINARY EXPRESSION
////////////////////////////////////////////////////////////////////////////

//#include "Tree.h"
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted.hpp>

BOOST_FUSION_ADAPT_STRUCT(VariableExpression, (std::string, _name))

namespace qi    = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phx   = boost::phoenix;

// Pass functions to boost
template <typename Iterator>
struct ExpressionParser : qi::grammar<Iterator, Expression(), ascii::space_type> 
{
    struct MakeBinaryExpression {
        template<typename,typename,typename> struct result { typedef BinaryExpression type; };

        template<typename C, typename L, typename R>
            BinaryExpression operator()(C op, L const& lhs, R const& rhs) const 
            { return BinaryExpression(op, lhs, rhs); }
    };

    phx::function<MakeBinaryExpression> makebinary;

    ExpressionParser() : ExpressionParser::base_type(expression) 
    {
        using namespace qi;
        expression =
            additive_expr                        [ _val = _1]
            ;

        additive_expr =
            primary_expr                         [ _val = _1 ]
            >> *(char_("-+*/") >> primary_expr)  [ _val = makebinary(_1, _val, _2)]
            ;

        primary_expr =
              ( '(' > expression > ')' )         [ _val = _1 ]
            | constant                           [ _val = _1 ]
            | variable                           [ _val = _1 ]
            ;

        constant = lexeme ["0x" >> hex] | double_ | int_;
        string   = '{' >> lexeme [ *~char_("}") ] > '}';
        variable = string | as_string [ alpha ];

        BOOST_SPIRIT_DEBUG_NODE(expression);
        BOOST_SPIRIT_DEBUG_NODE(additive_expr);

        BOOST_SPIRIT_DEBUG_NODE(primary_expr);
        BOOST_SPIRIT_DEBUG_NODE(constant);
        BOOST_SPIRIT_DEBUG_NODE(variable);
        BOOST_SPIRIT_DEBUG_NODE(string);
    }

    qi::rule<Iterator, Expression()        , ascii::space_type> expression;
    qi::rule<Iterator, Expression()        , ascii::space_type> additive_expr;

    qi::rule<Iterator, Expression()        , ascii::space_type> primary_expr;
    qi::rule<Iterator, ConstantExpression(), ascii::space_type> constant;
    qi::rule<Iterator, VariableExpression(), ascii::space_type> variable;
    qi::rule<Iterator, std::string()       , ascii::space_type> string;
};

void test(const std::string input, double a=0, double b=0)
{
    typedef std::string::const_iterator It;
    ExpressionParser<It> p;

    Expression e;
    It f(input.begin()), l(input.end());
    bool ok = qi::phrase_parse(f,l,p,ascii::space,e);

    std::cout << "Input:                "  << input            << "\n";
    std::cout << "Expression:           "  << e                << "\n";
    std::cout << "Parse success:        "  << std::boolalpha   << ok << "\n";
    std::cout << "Remaining unparsed:  '"  << std::string(f,l) << "'\n";

    std::cout << "(a, b):               "  << a << ", " << b   << "\n";

    VariableExpression::get("a") = a;
    VariableExpression::get("b") = b;
    std::cout << "Evaluation result:    "  << e.Evaluate()     << "\n";
    std::cout << "----------------------------------------\n";
}

int main() 
{
    test("3*8 + 6"); 
    test("3*(8+6)"); 
    test("0x1b"); 
    test("1/3"); 
    test(".3333 * 8e12");
    test("(2 * a) + b",    10,   7);
    test("(2 * a) + b",   -10, 800);
    test("(2 * {a}) + b", -10, 800);
    test("{names with spaces}");
}


Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum