访问带有额外参数的升压变体

Question

我正在尝试对布尔公式实施 Tseitin 转换。这个想法是您使用转换规则转换 CNF 中的布尔公式。例如，如果公式 f = l OR r，我们为每个公式分配一个新变量，比方说 v_f、v_l 和 v_r，然后我们将 f = l OR r 转换为(!v_f OR v_l OR v_r) 和 (v_f OR !v_l) 和 (v_f OR !v_r).

我使用类似（v_f、v_l 和 v_r 被 p、p1 和 p2 替换。m 是一个变量，它允许我们现在可以使用下一个变量）：

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

};

总的来说，我将此转换称为：boost::apply_visitor(tseitin(), result, 0);

但我遇到如下错误：error: no matching function for call to ‘apply_visitor(tseitin, expr&, int)’ boost::apply_visitor(tseitin(), result, 0); 并且：error: request for member ‘apply_visitor’ in ‘visitable’, which is of non-class type ‘const int’

我不太明白错误，你有什么想法吗？

您可能会注意到，我使用 How to calculate boolean expression in Spirit 和 boost spirit 教程来实现转换上的运算符。

我需要完整的代码，现在让我来。

提前致谢！

Answer 1

I don't really understand the error, do you have any ideas ?

您正在调用 boost::variant::apply_visitor 的二进制版本。但是你给它传递了一个变体和一个整数。正如错误消息所表明的那样，一个 int 是不可访问的。

要完成这项工作，只需绑定参数：

boost::apply_visitor(boost::bind(tseitin(), _1, 0), result);

这意味着_1占位符将接收变体元素并传递第二个参数。

您还想在 recurse 中完成此操作：

bool recurse(T const& v, U const& p) 
    { return boost::apply_visitor(boost::bind(*this, _1, p), v); }

更新

这是链接答案的演示，但使用额外的绑定参数而不是有状态的 printer 仿函数：

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

完整代码：

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

访问带有额外参数的升压变体

Visit boost variant with extra arguments

c++

boost

abstract-syntax-tree

boost-spirit

boost-variant

更新