c++ - How to calculate boolean expression in Spirit

Question

I found a really good example about boolean translator, * Boolean expression (grammar) parser in c++

What I am thinking now is to do a further step, translate (!T|F)&T into F or 0, so it is very convenient for calculating a very long boolean expression.

Is there some examples about this using spirit? What I have done is making a calculator first, and then let it calculate '(T+!F*T)', which equal to (T||!F&&T)but when I type (), there is an error. How to modify it? Thanks a lot!

#include <iostream>  
#include <stack>  
#include <boost/lexical_cast.hpp>  
#include <boost/config/warning_disable.hpp>  
#include <boost/spirit/include/qi.hpp>  
#include <boost/spirit/include/phoenix.hpp>  

using namespace std;  
namespace phoenix = boost::phoenix;  
namespace qi = boost::spirit::qi;  
namespace ascii = boost::spirit::ascii;  

struct calculator  
{  
    bool interpret(const string& s);  
    void do_neg();  
    void do_add();  
    void do_sub();  
    void do_mul();  
    void do_div();  
    void do_number(const char* first, const char* last);  
    int val() const;  
private:  
    stack<int> values_;  
    int *pn1_, n2_;  
    void pop_1();  
    void pop_2();  
};  

template <typename Iterator>  
struct calc_grammar : qi::grammar<Iterator, ascii::space_type>  
{  
    calc_grammar(calculator& calc)  
        : calc_grammar::base_type(add_sub_expr)  
        , calc_(calc)  
    {  
        using namespace qi;  
        using boost::iterator_range;  

#define LAZY_FUN0(f)        phoenix::bind(&calculator::f, calc_)  
#define LAZY_FUN2(f)        phoenix::bind(&calculator::f, calc_, phoenix::bind(&iterator_range<Iterator>::begin, qi::_1), phoenix::bind(&iterator_range<Iterator>::end, qi::_1))  

        add_sub_expr =  
            (  
                -lit('+') >> mul_div_expr |  
                (lit('-') >> mul_div_expr)[LAZY_FUN0(do_neg)]  
            ) >>  
            *(  
                lit('+') >> mul_div_expr[LAZY_FUN0(do_add)] |  
                lit('-') >> mul_div_expr[LAZY_FUN0(do_sub)]  
            ) >> eoi;  

        mul_div_expr =  
            basic_expr >>  
            *(   
                lit('*') >> basic_expr[LAZY_FUN0(do_mul)] |  
                lit('/') >> basic_expr[LAZY_FUN0(do_div)]  
            );  

        basic_expr =  
            raw[number][LAZY_FUN2(do_number)] |  
            lit('(') >> add_sub_expr >> lit(')');  

        number = lexeme[+digit];  
    }  
    qi::rule<Iterator, ascii::space_type> add_sub_expr, mul_div_expr, basic_expr, number;  
    calculator& calc_;  
};  

bool calculator::interpret(const string& s)  
{  
    calc_grammar<const char*> g(*this);  
    const char* p = s.c_str();  
    return qi::phrase_parse(p, p + s.length(), g, ascii::space);  
}  

void calculator::pop_1()  
{  
    pn1_ = &values_.top();  
}  

void calculator::pop_2()  
{  
    n2_ = values_.top();  
    values_.pop();  
    pop_1();  
}  

void calculator::do_number(const char* first, const char* last)  
{  
    string str(first, last);  
    int n = boost::lexical_cast<int>(str);  
    values_.push(n);  
}  

void calculator::do_neg()  
{  
    pop_1();  
    *pn1_ = -*pn1_;  
}  

void calculator::do_add()  
{  
    pop_2();  
    *pn1_ += n2_;  
}  

void calculator::do_sub()  
{  
    pop_2();  
    *pn1_ -= n2_;  
}  

void calculator::do_mul()  
{  
    pop_2();  
    *pn1_ *= n2_;  
}  

void calculator::do_div()  
{  
    pop_2();  
    *pn1_ /= n2_;  
}  

int calculator::val() const  
{  
    assert(values_.size() == 1);  
    return values_.top();  
}  

int main()  
{  
    for(;;){  
        cout << ">>> ";  
        string s;  
        getline(cin, s);  
        if(s.empty()) break;  
        calculator calc;  
        if(calc.interpret(s))  
            cout << calc.val() << endl;  
        else  
            cout << "syntax error" << endl;  
    }  
    return 0;  
}  

Answer 1

Here goes a quick and dirty demo based on my old Boolean Parser answer. This is a visitor that evaluates the AST you pass it:

struct eval : boost::static_visitor<bool> 
{
    eval() {}

    //
    bool operator()(const var& v) const 
    { 
        if (v=="T" || v=="t" || v=="true" || v=="True")
            return true;
        else if (v=="F" || v=="f" || v=="false" || v=="False")
            return false;
        return boost::lexical_cast<bool>(v); 
    }

    bool operator()(const binop<op_and>& b) const
    {
        return recurse(b.oper1) && recurse(b.oper2);
    }
    bool operator()(const binop<op_or>& b) const
    {
        return recurse(b.oper1) || recurse(b.oper2);
    }
    bool operator()(const unop<op_not>& u) const
    {
        return !recurse(u.oper1);
    } 

    private:
    template<typename T>
        bool recurse(T const& v) const 
        { return boost::apply_visitor(*this, v); }
};

bool evaluate(const expr& e) 
{ return boost::apply_visitor(eval(), e); }

I hope I can find some time later to explain. Note that _var is a misnomer now, since you wanted to treat all operands as literals. Also note that the evaluation of a literal is a bit ... quick and dirty right now :)

Full Code

Live On Coliru

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/variant/recursive_wrapper.hpp>
#include <boost/lexical_cast.hpp>

namespace qi    = boost::spirit::qi;
namespace phx   = boost::phoenix;

struct op_or  {};
struct op_and {};
struct op_not {};

typedef std::string var; 
template <typename tag> struct binop;
template <typename tag> struct unop;

typedef boost::variant<var, 
        boost::recursive_wrapper<unop <op_not> >, 
        boost::recursive_wrapper<binop<op_and> >,
        boost::recursive_wrapper<binop<op_or> >
        > expr;

template <typename tag> struct binop
{
    explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { }
    expr oper1, oper2;
};

template <typename tag> struct unop
{
    explicit unop(const expr& o) : oper1(o) { }
    expr oper1;
};

struct eval : boost::static_visitor<bool> 
{
    eval() {}

    //
    bool operator()(const var& v) const 
    { 
        if (v=="T" || v=="t" || v=="true" || v=="True")
            return true;
        else if (v=="F" || v=="f" || v=="false" || v=="False")
            return false;
        return boost::lexical_cast<bool>(v); 
    }

    bool operator()(const binop<op_and>& b) const
    {
        return recurse(b.oper1) && recurse(b.oper2);
    }
    bool operator()(const binop<op_or>& b) const
    {
        return recurse(b.oper1) || recurse(b.oper2);
    }
    bool operator()(const unop<op_not>& u) const
    {
        return !recurse(u.oper1);
    } 

    private:
    template<typename T>
        bool recurse(T const& v) const 
        { return boost::apply_visitor(*this, v); }
};

struct printer : boost::static_visitor<void> 
{
    printer(std::ostream& os) : _os(os) {}
    std::ostream& _os;

    //
    void operator()(const var& v) const { _os << v; }

    void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        _os << "(";
        boost::apply_visitor(*this, l);
        _os << op;
        boost::apply_visitor(*this, r);
        _os << ")";
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << "(";
        _os << "!";
        boost::apply_visitor(*this, u.oper1);
        _os << ")";
    } 
};

bool evaluate(const expr& e) 
{ return boost::apply_visitor(eval(), e); }

std::ostream& operator<<(std::ostream& os, const expr& e) 
{ boost::apply_visitor(printer(os), e); return os; }

    template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr(), Skipper>
{
        parser() : parser::base_type(expr_)
        {
            using namespace qi;

            expr_  = or_.alias();

            or_  = (and_ >> '|'  >> or_ ) [ _val = phx::construct<binop<op_or > >(_1, _2) ] | and_   [ _val = _1 ];
            and_ = (not_ >> '&' >> and_)  [ _val = phx::construct<binop<op_and> >(_1, _2) ] | not_   [ _val = _1 ];
            not_ = ('!' > simple       )  [ _val = phx::construct<unop <op_not> >(_1)     ] | simple [ _val = _1 ];

            simple = (('(' > expr_ > ')') | var_);
            var_ = qi::lexeme[ +(alpha|digit) ];

            BOOST_SPIRIT_DEBUG_NODE(expr_);
            BOOST_SPIRIT_DEBUG_NODE(or_);
            BOOST_SPIRIT_DEBUG_NODE(and_);
            BOOST_SPIRIT_DEBUG_NODE(not_);
            BOOST_SPIRIT_DEBUG_NODE(simple);
            BOOST_SPIRIT_DEBUG_NODE(var_);
        }

        private:
        qi::rule<It, var() , Skipper> var_;
        qi::rule<It, expr(), Skipper> not_, and_, or_, simple, expr_; 
};

int main() 
{
    const std::string inputs[] = { 
        std::string("true & false;"),
        std::string("true & !false;"),
        std::string("!true & false;"),
        std::string("true | false;"),
        std::string("true | !false;"),
        std::string("!true | false;"),

        std::string("T&F;"),
        std::string("T&!F;"),
        std::string("!T&F;"),
        std::string("T|F;"),
        std::string("T|!F;"),
        std::string("!T|F;"),
        std::string("") // marker
    };

    for (const std::string *i = inputs; !i->empty(); ++i)
    {
        typedef std::string::const_iterator It;
        It f(i->begin()), l(i->end());
        parser<It> p;

        try
        {
            expr result;
            bool ok = qi::phrase_parse(f,l,p > ';',qi::space,result);

            if (!ok)
                std::cerr << "invalid input
";
            else
            {
                std::cout << "result:" << result << "
";
                std::cout << "evaluated:" << evaluate(result) << "
";
            }

        } catch (const qi::expectation_failure<It>& e)
        {
            std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'
";
        }

        if (f!=l) std::cerr << "unparsed: '" << std::string(f,l) << "'
";
    }

    return 0; 
}

Output:

result: (true & false)
evaluated:  0
result: (true & (!false))
evaluated:  1
result: ((!true) & false)
evaluated:  0
result: (true | false)
evaluated:  1
result: (true | (!false))
evaluated:  1
result: ((!true) | false)
evaluated:  0
result: (T & F)
evaluated:  0
result: (T & (!F))
evaluated:  1
result: ((!T) & F)
evaluated:  0
result: (T | F)
evaluated:  1
result: (T | (!F))
evaluated:  1
result: ((!T) | F)
evaluated:  0