#include <iostream>
#include <string>
#include <cctype>
#include <exception>

#include <boost/variant.hpp>
#include <boost/pool/object_pool.hpp>

namespace parser
{
    struct Lex_unit
    {
        enum Type
        { constant, op_low, op_high, x, opth, cpth, undef
        } type;

        boost::variant < char, double > attribut; // constant or operator

        Lex_unit(char op)
        {
            if(op == '+' || op == '-')
                type = op_low;
            else if(op == '*' || op == '/')
                type = op_high;
            else throw std::string("unexpected operator");
            attribut = op;
        }

        Lex_unit(double cst) : attribut(cst)
        { type = constant; }

        Lex_unit(Type t)
        {
            if(t != x && t != opth && t != cpth)
                throw std::string("unexpected token type");
            type = t;
        }

        Lex_unit() : type(undef) {}
    }; // struct Lex_unit

    struct Lexer
    {
        typedef std::string::const_iterator Iterator;
        Iterator begin, end;

        Lexer(Iterator b, Iterator e)
            : begin(b), end(e) {}

        bool match(char c)
        {
            if(*begin != c)
                return false;
            ++begin;
            return true;
        }

        Lex_unit next_unit()
        {
            while(begin != end && std::isspace(*begin))
                ++begin;

            if(begin == end)
                return Lex_unit();

            if(std::isdigit(*begin))
            {
                double accumulator = 0;
                do accumulator = 10 * accumulator + (*begin - '0');
                    while(++begin != end && std::isdigit(*begin));
                if(begin != end && *begin == '.')
                {
                    double dec = 10;
                    for(; ++begin != end && std::isdigit(*begin); dec *= 10)
                        accumulator += (*begin - '0') / dec;
                }
                return Lex_unit(accumulator);
            }

            char ret = *begin;
            if(match('+') || match('-') || match('*') || match('/'))
                return Lex_unit(ret);
            if(match('('))
                return Lex_unit(Lex_unit::opth);
            if(match(')'))
                return Lex_unit(Lex_unit::cpth);
            if(match('x'))
                return Lex_unit(Lex_unit::x);

            throw std::string("lexer : unexpected character");
        }
    }; // struct Lexer

    namespace ast
    {
        namespace x_value
        { double val; }

        struct Expr
        {
            virtual ~Expr() {}
            virtual double eval()
            { throw std::string("undefined ast node"); }
        };

        struct Binary_op : public Expr
        {
            char oprt;
            Expr* opr1, *opr2;
            Binary_op(char op, Expr* op1, Expr* op2)
                : oprt(op), opr1(op1), opr2(op2) {}

            double eval()
            {
                double r1 = opr1 -> eval();
                double r2 = opr2 -> eval();
                switch(oprt)
                {
                    case '+' : return r1 + r2;
                    case '-' : return r1 - r2;
                    case '*' : return r1 * r2;
                    case '/' : return r1 / r2;
                }
                throw std::string("ast eval : unexpected operator");
            }
        };

        struct Constant : public Expr
        {
            double value;
            Constant(double val) : value(val) {}

            double eval()
            { return value; }
        };

        struct X : public Expr
        {
            double eval()
            { return x_value::val; }
        };

        namespace pool
        {
            boost::object_pool < Binary_op > op_pool;
            boost::object_pool < Constant > const_pool;
            boost::object_pool < X > x_pool;
        }
    } // namespace ast

    struct Parser
    {
        typedef Lexer::Iterator Iterator;
        Lexer lexer;
        Lex_unit unit;

        Parser(Iterator begin, Iterator end)
            : lexer(begin, end) {}

        void next_unit()
        { unit = lexer.next_unit(); }

        char ret_op()
        {
            char ret = boost::get < char >(unit.attribut);
            next_unit();
            return ret;
        }

        double ret_const()
        {
            double ret = boost::get < double >(unit.attribut);
            next_unit();
            return ret;
        }

        ast::Expr* fact()
        {
            using namespace ast;
            if(unit.type == Lex_unit::constant)
                return new (pool::const_pool.malloc()) Constant(ret_const());
            if(unit.type == Lex_unit::opth)
            {
                next_unit();
                Expr* e = expr();
                if(unit.type != Lex_unit::cpth)
                    throw std::string("missing closing parenthesis");
                next_unit();
                return e;
            }
            if(unit.type == Lex_unit::x)
            {
                next_unit();
                return new (pool::x_pool.malloc()) X;
            }
            throw std::string("parser : unexpected factor form");
        }

        ast::Expr* term()
        {
            using namespace ast;
            Expr* t = fact();
            while(unit.type == Lex_unit::op_high)
            {
                char ret = ret_op();
                t = new (pool::op_pool.malloc()) Binary_op(ret, t, fact());
            }
            return t;
        }

        ast::Expr* expr()
        {
            using namespace ast;
            Expr* t = term();
            while(unit.type == Lex_unit::op_low)
            {
                char ret = ret_op();
                t = new (pool::op_pool.malloc()) Binary_op(ret, t, term());
            }
            return t;
        }

        ast::Expr* parse()
        {
            next_unit();
            ast::Expr* ast = expr();
            if(lexer.begin != lexer.end)
                throw std::string("incomplete parsing");
            return ast;
        }
    }; // struct Parser
} // namespace parser

double eval(const std::string& expr, double x)
{
    using namespace parser;
    Parser pars(expr.begin(), expr.end());
    ast::Expr* ast = pars.parse();
    ast::x_value::val = x;
    return ast -> eval();
}

int main()
{
    try
    { std::cout << eval("4.2*x+(x-(1.00))", 4); } // 19.8
    catch(const std::exception& e)
    { std::cerr << e.what(); }
    catch(const std::string& s)
    { std::cerr << s; }
    return 0;
}