string to Boolean expression is not working c++

Question

I have a following code to evaluate a Boolean string based on an string input.

The code supposed to work like this:

Boolean string: "((0|1)&3);"

Sting input: "101"  

how's it working? each character in the input string is supposed to be substituted by corresponding character in Boolean string.

for example:

• 1 in the input string by 0 in Boolean string

• 0 in the input string by 1 in Boolean string

• 1 in the input string by 3 in Boolean string

I know it is confusing, My problem is that the code was used to work for many cases, but I don't understand why it is not working for above example.

I added the live version for editing here.

#include <iostream>
#include <fstream>
#include <vector>

#include <boost/lexical_cast.hpp>
#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>


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 eval2 : boost::static_visitor<bool> 
{
    eval2(const std::string& pk): pkey(pk) { iter = 0; }

    //
    bool operator()(const var& v) const 
    { 
      std:: cout << "**** " << v << "\titer: " << iter << std::endl;
      iter ++;
      return boost::lexical_cast<bool>(pkey[iter-1]); 
    }

    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:
    mutable int iter;
    const std::string pkey;
    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 evaluate2(const expr& e, const std::string s) 
{ 
  return boost::apply_visitor(eval2(s), 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_ ) [ qi::_val = phx::construct<binop<op_or > >(qi::_1, qi::_2) ] | and_   [ qi::_val = qi::_1 ];
            and_ = (not_ >> '&' >> and_)  [ qi::_val = phx::construct<binop<op_and> >(qi::_1, qi::_2) ] | not_   [ qi::_val = qi::_1 ];
            not_ = ('!' > simple       )  [ qi::_val = phx::construct<unop <op_not> >(qi::_1)     ] | simple [ qi::_val = qi::_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_; 
};

bool string2BooleanExe(std::string bStatement, std::string bKey)
{
  typedef std::string::const_iterator It;
  It f(bStatement.begin()), l(bStatement.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";
      bool returnResult = evaluate2(result, bKey);
      std::cout << "evaluated:\t" << returnResult << "\n";
      return returnResult;
      }

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

int main()
{
    bool res = string2BooleanExe("((0|1)&3);", "101");
    std::cout << "res: " << res << std::endl;
    return 0;
}

Please note I can only use C++03.

Answer 1

So you want variables. And they are implicit. And you denote them with integers in the expression. Yes, that's confusing, but why not, I guess.

The grammar suggests that variables could be any length of alphanumeric characters, though. Let's do this, and fix the sample to be:

bool res = string2BooleanExe("((a|b)&c);", {
        { "a", true }, { "b", false }, { "c", true } }); // was: 101

Now in your implementation there are two big problems:

1. you are using names 0, 1, 2 for the placeholders in the source expression but these are ignored (this means that ((0|1)&2) is functionally equivalent to ((1|2)&0)... I doubt that's what anyone wanted)

2. your eval2¹ visitor is stateful. You need to pass and use it by reference if you're going to retain state. Alternatively, make sure your copy constructor actually copies the value of iter

Here's my take on things, using

typedef std::map<std::string, bool> VarMap;

Let's use it in the evaluator visitor:

struct evaluator : boost::static_visitor<bool> 
{
    evaluator(VarMap const& pk) : pk(pk) { }

    bool operator()(const var& v) const { return pk.at(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); }
    const VarMap pk;
};

Splitting the evaluate and parse functions:

static const parser<std::string::const_iterator> s_parser_instance;
expr parse(std::string const& bStatement) {
    std::string::const_iterator f = bStatement.begin(), l = bStatement.end();

    expr parsed;
    qi::parse(f, l, s_parser_instance, parsed);

    return parsed;
}

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

Now let's see the full demo

Full Demo

Live On Coliru

//#define BOOST_SPIRIT_DEBUG
#include <iostream>
#include <fstream>
#include <vector>

#include <boost/lexical_cast.hpp>
#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>

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

typedef std::map<std::string, bool> VarMap;

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 evaluator : boost::static_visitor<bool> 
{
    evaluator(VarMap const& pk) : pk(pk) { }

    bool operator()(const var& v) const { return pk.at(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); }
    const VarMap pk;
};

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

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

template <typename It>
struct parser : qi::grammar<It, expr()>
{
    parser() : parser::base_type(start) {
        using namespace qi;

        start  = skip(space) [expr_ > ';' > eoi];

        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_   = lexeme[ +(alpha|digit) ];

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

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

static const parser<std::string::const_iterator> s_parser_instance;
expr parse(std::string const& bStatement) {
    std::string::const_iterator f = bStatement.begin(), l = bStatement.end();

    expr parsed;
    qi::parse(f, l, s_parser_instance, parsed);

    return parsed;
}

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

void test(std::string const& expression, VarMap const& vars, bool expected) {
    try {
        std::cout << "'" << expression << "'";

        expr parsed = parse(expression);
        std::cout << " -> " << parsed;

        bool actual = evaluate(parsed, vars);
        std::cout 
            << " - evaluates to " << std::boolalpha << actual
            << (expected == actual? " Correct." : " INCORRECT!!!")
            << "\n";

    } catch(std::exception const& e) {
        std::cout << " EXCEPTION(" << e.what() << ")\n";
    }
}

int main() {
    VarMap vars;
    vars["a"] = true;
    vars["b"] = false;
    vars["c"] = true;

    test("a;", vars, true);
    test("b;", vars, false);
    test("c;", vars, true);

    test("((a|b)&c);", vars, true);

    vars["c"] = false;
    test("((a|b)&c);", vars, false);

    // let's use an undefined variable - should throw
    test("((z|y)&x);", vars, false|true);

    // you CAN still use confusing numeric placeholders:
    vars["0"] = true;
    vars["1"] = false;
    vars["2"] = true;
    test("((0|1)&2);", vars, true);
    test("((2|0)&1);", vars, false);
    test("((1|0)&2);", vars, true);

    // note you can also have "special variables"; no need for single-letter names
    vars["TRUE"] = true;
    vars["FALSE"] = false;
    test("TRUE | FALSE;", vars, true);
    test("TRUE & FALSE;", vars, false);
}

Prints:

'a;' -> a - evaluates to true Correct.
'b;' -> b - evaluates to false Correct.
'c;' -> c - evaluates to true Correct.
'((a|b)&c);' -> ((a | b) & c) - evaluates to true Correct.
'((a|b)&c);' -> ((a | b) & c) - evaluates to false Correct.
'((z|y)&x);' -> ((z | y) & x) EXCEPTION(map::at)
'((0|1)&2);' -> ((0 | 1) & 2) - evaluates to true Correct.
'((2|0)&1);' -> ((2 | 0) & 1) - evaluates to false Correct.
'((1|0)&2);' -> ((1 | 0) & 2) - evaluates to true Correct.
'TRUE | FALSE;' -> (TRUE | FALSE) - evaluates to true Correct.
'TRUE & FALSE;' -> (TRUE & FALSE) - evaluates to false Correct.

---

¹ FIX BAD NAMING. Also, single-responsibility. Make a parse function and an evaluate function. Put ';' and the skipper inside the grammar. Check for qi::eoi inside the grammar. Propagate exceptions instead of doing magic console output inside your parse/evaluate function.