- android - RelativeLayout 背景可绘制重叠内容
- android - 如何链接 cpufeatures lib 以获取 native android 库?
- java - OnItemClickListener 不起作用,但 OnLongItemClickListener 在自定义 ListView 中起作用
- java - Android 文件转字符串
首先,如果使用 Boost Variant 或 Utree 更容易,那么我会和他们一起解决,我会尝试在另一个主题中解决我的问题。但是,我非常希望能够像下面这样构建一棵树。
背景,如果您想直接进入问题,请忽略:我希望能够构建一个表达式树来解析类似
"({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)
)
树.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 的情况下构建了这样的树。
如果我违反了惯例,我也很抱歉,对于我的格式,我试图让它尽可能可读。
最佳答案
我不清楚您对(递归)变体的提示是什么,但这里有一个变体伴随着您希望使用动态分配的节点使用“老式”树构建的愿望:
我在你的语法中故意回避了运算符优先级的问题,因为
您可以在其他答案中了解这些:
注意我的做法
makebinary
现在的 Actor 。 请注意现在如何支持运算符链 (1+2+5+6-10):
additive_expr =
primary_expr [ _val = _1 ]
>> *(char_("-+*/") >> primary_expr) [ _val = makebinary(_1, _val, _2)]
;
我添加了 {var}
, /
, *
和 (expr)
支持
为显示添加序列化(Print
虚拟方法,operator<<
)(为了显示方便,BinaryExpression 现在存储 operator
而不是结果 method
)
Expression
至 AbstractExpression
(并使 de constructor protected)PrimaryExpression
至 Expression
(现在这是您的主要表达式数据类型)static
中简单地存储变量 map
qi::symbols
和variable
)使用模板化构造函数技巧可以非常轻松地从不同的解析类型构造表达式:
struct Expression : AbstractExpression {
template <typename E>
Expression(E const& e) : _e(make_from(e)) { } // cloning the expression
// ...
};
足以有效地支持例如:
primary_expr =
( '(' > expression > ')' ) [ _val = _1 ]
| constant [ _val = _1 ]
| variable [ _val = _1 ]
;
为了好玩还包含了一些测试用例:
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
----------------------------------------
// #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}");
}
关于c++ - 在 Spirit:Qi 中构建自定义表达式树(没有 Utree 或 Boost::Variant),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13056893/
我正在将一个手写解析器迁移到 Boost.Spirit (2.5.4)。第一印象是积极的,但由于我使用的是 C++17,X3 似乎是一个非常有吸引力的选择。 幸运的是,有很多关于 X3 的可用资源:
是否可以使用 boost::spirit::qi 来解析以下内容? A_B --> (A, B) A_B_C --> (A_B, C) A_B_C_D --> (A_B_
我正在尝试解析一种类似 lisp 的语言,它具有一些通用功能的语法糖。例如,plus 函数可以写成 (+ 1 2) 或 1 + 2。我认为在尝试解释语言之前消除句法糖会显着促进解释过程,因为那样的话,
我正在尝试解析一种类似 lisp 的语言,它具有一些通用功能的语法糖。例如,plus 函数可以写成 (+ 1 2) 或 1 + 2。我认为在尝试解释语言之前消除句法糖会显着促进解释过程,因为那样的话,
我想使用解析后的值作为循环解析器的输入。 语法定义了一个 header ,它指定了以下字符串的(可变)大小。例如,假设以下字符串是某个解析器的输入。 12\r\nTest Payload 解析器应提取
我正在编写 DSL 并使用 Boost Spirit 词法分析器来标记我的输入。在我的语法中,我想要一个类似于此的规则(其中 tok 是词法分析器): header_block = tok.n
我有以下精神语法。我正在尝试在 struct myresult 中创建 AST 节点的向量使用标准 push_back(at_c(qi::_val), qi::_1)但出现编译错误(见下文)。 typ
需要为 std::pair 对象提供类型为 boost::variant 的对象的值。您将如何使用其他资源来实现这个想法?下面还有其他方法吗? struct aggr_pair_visitor
我有一个词法分析器,基于该词法分析器,我现在想创建一个使用该词法分析器生成的标记的语法。我尝试改编我发现的一些示例,现在我有一些可以编译和工作的东西至少有一点,但我的一个应该失败的测试却没有。现在我想
当我使用此 qi 语法从 Lex 接受标记时: pair %= token(ID_MARKER) >> ':' >> atom >> ',' >> atom
如何解析可能包含 double 或 int 的字符串,具体取决于是否设置了点。例如。 6.0是double类型,6是int类型。规则是 rule,skipper> r = qi::double_|qi
请帮助我诊断以下错误。我有一个简单的语法: struct json_start_elem_grammar_object : qi::grammar { json_start_elem_gramma
作为使用 Boost.Spirit 的更大语法的第一阶段,我尝试解析“true”和“false”以生成相应的 bool 值,true 和 false. 我正在使用 Spirit.Lex 对输入进行标记
我正在尝试解析一个也可以包含标识符的表达式并将每个元素推送到 std::vector 中,我想出了以下语法: #include #include #include #include name
我正在为 if 函数实现生产规则: qi::rule f_if; f_if = qi::ascii::string("if") >> qi::char_('(')
我编写了这段代码示例并期望它打印OPERATION( OPERATOR(aaa) ID(bbb) ) 但我只得到OPERATION ( OPERATOR(aaa) )反而。 result2 和 it1
我的数据定义为: std::string data("START34*23*43**"); 我的语法: "START" >> boost::spirit::hex % '*' 题: 如何解析有两颗星的
我编写了这段代码示例并期望它打印OPERATION( OPERATOR(aaa) ID(bbb) ) 但我只得到OPERATION ( OPERATOR(aaa) )反而。 result2 和 it1
我需要解析一个键值对,其中键本身是示例中的固定字符串lke'cmd'。不幸的是qi::lit没有综合属性,并且qi::char_没有解析固定的字符串。 以下代码无法编译。执行后,我需要那个result
我正在尝试编写精神规则,但我无法弄清楚这个新规则的属性是什么。 以下代码按我预期的方式工作。 #include #include #include #include #include nam
我是一名优秀的程序员,十分优秀!