First of all, if it is easier using either Boost Variant or Utree, then I will agree with them, and I will try to solve my problems with them in another topic. However, I would really like to be able to build a tree, as I have below.
Background, ignore if you want to go straight to the problem: I would like to be able to build an expression tree that parses something like
"({a} == 0) && ({b} > 5)"
or standard math expression
"(2 * a) + b"
Then I will determine what a and b are, before I evaluate my tree, something like this:
a = 10; double val = myExpression->Evaluate();
My problem arises when I try to create an attempt to parse a string in my expression tree. I use the abstract class "Expression", which then displays the expressions "Variable", "Constant" and "Binary" (it will also be unary, but it should not affect my problem. I am having problems adding to the tree using my rules , so I'm obviously doing something wrong, it's hard for me to wrap my head around attributes.
My tree looks like this (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(); };
Tree.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; }
Now, if I build a tree manually, everything works fine, so I don’t think the problem is with how it is structured.
Here is Grammar.h (A lot of comments from where I tried different things, I could delete them, but it may seem to me that I tried / where I want to go with it)
#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 ; };
So this is really hacked, but hopefully it will show what I'm trying to achieve. Any advice or advice would be really appreciated. Is there an example when someone created such a tree without using a variant or utree.
Also sorry if Iv violated the agreement and for my formatting I tried to make it as readable as possible.