首先,如果使用Boost Variant或Utree更容易的话,我会选择它们,并在另一个主题中尝试解决我的问题。然而,我非常希望能够像下面一样构建树。
背景:如果您想直接转到问题,请忽略本段。我想构建一个表达式树,它可以解析类似于下面的内容。
或者一个标准的数学表达式。
我的问题出在我尝试将字符串解析成表达式树时。我使用了一个抽象类"Expression",然后派生出"Variable"、"Constant"和"Binary"表达式 (它还将执行一元运算,但它不应该影响我的问题)。我在使用规则添加到树时经常遇到问题,所以我显然做错了什么。我很难理解这些属性。
我的树如下(Tree.h):
现在如果我手动构建树,一切都运行良好,因此我认为它的结构没有问题。
以下是Grammar.h文件(有很多注释,这些注释记录了我尝试过的各种方法,我可以删除它们,但可能值得展示我想要做什么/我想要达到的目标)。
背景:如果您想直接转到问题,请忽略本段。我想构建一个表达式树,它可以解析类似于下面的内容。
"({a} == 0) && ({b} > 5)"
或者一个标准的数学表达式。
"(2 * a) + b"
在评估我所定义的树之前,我会先定义变量a和b,类似于这样:
a = 10;
double val = myExpression->Evaluate();
我的问题出在我尝试将字符串解析成表达式树时。我使用了一个抽象类"Expression",然后派生出"Variable"、"Constant"和"Binary"表达式 (它还将执行一元运算,但它不应该影响我的问题)。我在使用规则添加到树时经常遇到问题,所以我显然做错了什么。我很难理解这些属性。
我的树如下(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)
)
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;
}
现在如果我手动构建树,一切都运行良好,因此我认为它的结构没有问题。
以下是Grammar.h文件(有很多注释,这些注释记录了我尝试过的各种方法,我可以删除它们,但可能值得展示我想要做什么/我想要达到的目标)。
#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
;
};
这段代码虽然有点混乱,但希望能够展示我想要实现的内容。如果您有任何建议或提示,将不胜感激。是否有人已经构建了这样的树形结构,而没有使用variant或utree呢?
如果我违反了惯例或格式不正确,请多多包涵,我尽力使其易于阅读。