I am trying to implement the Tseitin transformation over boolean formulas. The idea is that you transform boolean formulas in CNF, using transformation rules. For example, if the formula f = l OR r, we assign to each formula a new variable, let's say v_f, v_l and v_r, and we transform f = l OR r into (!v_f OR v_l OR v_r) AND (v_f OR !v_l) AND (v_f OR !v_r).
I use something like (v_f, v_l and v_r are replaced by p, p1 and p2. m is a variable that permits us to now what next variable we can use) :
int m = 0;
std::vector<std::vector<int> > formules;
struct op_or {};
struct op_and {};
struct op_not {};
struct op_impl {};
typedef int 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> >,
boost::recursive_wrapper<binop<op_impl> >
> 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 tseitin : boost::static_visitor<void>
{
tseitin() {}
void operator()(const var& v, int p = 0) {}
void operator()(const binop<op_and>& b, int p = m++) { proceed(0, b.oper1, b.oper2, p); }
void operator()(const binop<op_or>& b, int p = m++) { proceed(1, b.oper1, b.oper2, p);}
void operator()(const unop<op_not>& u, int p = m++) {}
void proceed(int nop, const expr& l, const expr& r, int p)
{
int p1 = m+1;
int p2 = m+2;
m += 2;
// Do the transformation
recurse(l, p1);
recurse(r, p2);
}
private:
template<typename T, typename U>
bool recurse(T const& v, U const& p)
{ return boost::apply_visitor(*this, v, p); }
};
And in the main, I call this transformation with : boost::apply_visitor(tseitin(), result, 0);
But I encounter errors like : error: no matching function for call to ‘apply_visitor(tseitin, expr&, int)’
boost::apply_visitor(tseitin(), result, 0);
And : error: request for member ‘apply_visitor’ in ‘visitable’, which is of non-class type ‘const int’
I don't really understand the error, do you have any ideas ?
As you may notice, I used How to calculate boolean expression in Spirit and boost spirit tutorial to implement the operators over the transformation.
I you need the whole code, let me now.
Thanks in advance !
I don't really understand the error, do you have any ideas ?
You are calling the binary version of boost::variant::apply_visitor. But you pass it a variant and an int. An int, as the error message announces, is not visitable.
To make this work, just bind the argument:
boost::apply_visitor(boost::bind(tseitin(), _1, 0), result);
This means that the _1 placeholder will receive the variant element and the second parameter is passed through.
You will also want to carry this through in recurse:
bool recurse(T const& v, U const& p)
{ return boost::apply_visitor(boost::bind(*this, _1, p), v); }
Here's the demo of the linked answer, but using extra bound arguments instead of a stateful printer functor:
struct printer : boost::static_visitor<void>
{
//
void operator()(std::ostream& os, const var& v) const { os << v; }
void operator()(std::ostream& os, const binop<op_and>& b) const { print(os, " & ", b.oper1, b.oper2); }
void operator()(std::ostream& os, const binop<op_or >& b) const { print(os, " | ", b.oper1, b.oper2); }
void print(std::ostream& os, const std::string& op, const expr& l, const expr& r) const
{
os << "(";
boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), l);
os << op;
boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), r);
os << ")";
}
void operator()(std::ostream& os, const unop<op_not>& u) const
{
os << "(";
os << "!";
boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), u.oper1);
os << ")";
}
};
Full Code:
#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>
#include <boost/bind.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>
{
//
void operator()(std::ostream& os, const var& v) const { os << v; }
void operator()(std::ostream& os, const binop<op_and>& b) const { print(os, " & ", b.oper1, b.oper2); }
void operator()(std::ostream& os, const binop<op_or >& b) const { print(os, " | ", b.oper1, b.oper2); }
void print(std::ostream& os, const std::string& op, const expr& l, const expr& r) const
{
os << "(";
boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), l);
os << op;
boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), r);
os << ")";
}
void operator()(std::ostream& os, const unop<op_not>& u) const
{
os << "(";
os << "!";
boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), 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(boost::bind(printer(), boost::ref(os), _1), 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 > >(qi::_1, qi::_2) ] | and_ [ _val = qi::_1 ];
and_ = (not_ >> '&' >> and_) [ _val = phx::construct<binop<op_and> >(qi::_1, qi::_2) ] | not_ [ _val = qi::_1 ];
not_ = ('!' > simple ) [ _val = phx::construct<unop <op_not> >(qi::_1) ] | simple [ _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_;
};
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;
}