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;  
}  

Huntlee

I unfortunately haven’t got the time to write up an answer but you can make the code much simpler. In fact, you can directly adapt the example in the answer you link to. The only thing that needs changing is the printer visitor. Instead of void it needs to return bool and instead of printing the nodes it needs to calculate the results. That’s literally all there is to it. – Stalker

@KonradRudolph Cheers. You're completely right. I will see what I can do while time permits :) – Myocarditis

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\n";
            else
            {
                std::cout << "result:\t" << result << "\n";
                std::cout << "evaluated:\t" << evaluate(result) << "\n";
            }

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

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

    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

Myocarditis

@Myocarditis Thanks for your nice answer. but my [question][1] is replacing a vector with unknown size and for general boolean string statement. [1]: #37661327 – Multiplier