Создание собственного дерева выражений в духе: Ци (без Utree или Boost :: Variant)

Мне не ясно, каково ваше понимание (рекурсивных) вариантов, но вот вариант, который согласуется с вашим желанием использовать «старомодное» построение дерева с использованием динамически распределенных узлов:

• http://liveworkspace.org/code/3VS77n$0

Я целенаправленно обошел проблему приоритет оператора в вашей грамматике, потому что

• ваша грамматика была неполной
• Я не знаю желаемой семантики (в конце концов, вы, похоже, также поддерживаете булеву оценку, но я не уверен, как)

• Вы можете узнать об этом в других ответах:

  • Анализатор логических выражений (грамматика) в c ++
  • Boost :: анализатор выражений духа
  • Ошибка компиляции с boost :: spirit parser показывает альтернативный подход

Обратите внимание, как я

• устранены повсеместные утечки памяти с помощью shared_ptr (вы можете использовать Увеличение один, если у вас нет библиотеки TR1)
• Я удалил ошибочное повторное использование определенного экземпляра BinaryExpression как ленивый актер феникс. Вместо этого я сделал местный makebinary Актер сейчас.

• Обратите внимание, как теперь поддерживаются цепочки операторов (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 сейчас)

• Поэтому теперь вы можете использовать BOOST_SPIRIT_DEBUG (раскомментировать первую строку)
• Я переименовал Expression в AbstractExpression (и сделал де конструктор защищенный)
• Я переименовал PrimaryExpression в Expression (а теперь это ваш главный тип данных выражения)
• Я покажу, как хранить упрощенно переменные в static карта
  • обязательно взгляните на qi::symbols а также
  • например Как добавить символы qi :: в грамматику<Итератора, двойной ()>?
• Использует гораздо меньше адаптация структуры слияния (только для 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}");
}