给定一个表达式模板树，我想在处理它之前创建一个新的优化树。考虑以下乘法运算示例:

a * b * c * d,

由于 operator* 的从左到右的结合性，它产生了表达式树:

(((a * b) * c) * d).

我想生成一个转换后的表达式树，其中乘法从右到左发生:

(a * (b * (c * d))).

考虑二进制表达式类型:

template<typename Left, typename Right>
struct BinaryTimesExpr
{
    BinaryTimesExpr() = default;
    BinaryTimesExpr(const BinaryTimesExpr&) = default;
    BinaryTimesExpr(BinaryTimesExpr&&) = default;
    BinaryTimesExpr(Left&& l, Right&& r) : left(forward<Left>(l)), right(forward<Right>(r)) {}

    BinaryTimesExpr& operator=(const BinaryTimesExpr&) = default;
    BinaryTimesExpr& operator=(BinaryTimesExpr&&) = default;

    Left left;
    Right right;
};

定义乘法运算符operator*:

template<typename Left, typename Right>
BinaryTimesExpr<Constify<Left>, Constify<Right>> operator*(Left&& l, Right&& r)
{
    return {forward<Left>(l), forward<Right>(r)};
}

其中 Constify 定义为:

template<typename T> struct HelperConstifyRef     { using type = T;  };
template<typename T> struct HelperConstifyRef<T&> { using type = const T&; };
template<typename T>
using ConstifyRef = typename HelperConstifyRef<T>::type;

并用于确保在从左值构造时具有 const 左值引用的子表达式，以及在从右值构造时复制(通过复制/移动)右值的子表达式。

定义转换函数，用前面的条件创建一个新的表达式模板树:

template<typename Expr>
auto Transform(const Expr& expr) -> Expr
{
    return expr;
}

template<typename Left, typename Right>
auto Transform(const BinaryTimesExpr<Left, Right>& expr) -> type(???)
{
    return {(Transform(expr.left), Transform(expr.right))};
}

template<typename Left, typename Right>
auto Transform(const BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right>& expr) -> type(???)
{
    return Transform({Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}}); // this sintax is invalid...how can I write this?
}

我的问题是:

1) 如何确定 Transform 函数的返回类型？我试过使用类型特征，例如:

template<typename Expr>
struct HelperTransformedExpr
{
    using type = Expr;
};

template<typename Left, typename Right>
struct HelperTransformedExpr<BinaryTimesExpr<Left, Right>>
{
    using type = BinaryTimesExpr<typename HelperTransformedExpr<Left>::type, typename HelperTransformedExpr<Right>::type>;
};

template<typename LeftLeft, typename LeftRight, typename Right>
struct HelperTransformedExpr<BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right>>
{
    using type = BinaryTimesExpr<typename HelperTransformedExpr<LeftLeft>::type,
        BinaryTimesExpr<typename HelperTransformedExpr<LeftRight>::type, typename HelperTransformedExpr<Right>::type>>;
};

template<typename Expr>
using TransformedExpr = typename HelperTransformedExpr<Expr>::type;

但不知道如何应用它来解决我下面的问题 (2)。

2) 如何编写递归行:

return Transform({Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}});

3) 这个问题有更干净的解决方案吗？

编辑: DyP 为上述问题提供了部分解决方案。以下是我基于他的回答的完整解决方案:

template<typename Expr>
auto Transform(const Expr& expr) -> Expr
{
    return expr;
}

template<typename Left, typename Right>
auto Transform(BinaryTimesExpr<Left, Right> const& expr)
-> decltype(BinaryTimesExpr<decltype(Transform(expr.left)), decltype(Transform(expr.right))>{Transform(expr.left), Transform(expr.right)})
{
    return BinaryTimesExpr<decltype(Transform(expr.left)), decltype(Transform(expr.right))>{Transform(expr.left), Transform(expr.right)};
}

template<typename LeftLeft, typename LeftRight, typename Right>
auto Transform(BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right> const& expr)
-> decltype(Transform(BinaryTimesExpr<decltype(Transform(expr.left.left)), BinaryTimesExpr<decltype(Transform(expr.left.right)), decltype(Transform(expr.right))>>{Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}}))
{
    return Transform(BinaryTimesExpr<decltype(Transform(expr.left.left)), BinaryTimesExpr<decltype(Transform(expr.left.right)), decltype(Transform(expr.right))>>{Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}});
}

int main()
{
    BinaryTimesExpr<int, int> beg{1,2};
    auto res = beg*3*4*5*beg;
    std::cout << res << std::endl;
    std::cout << Transform(res) << std::endl;
}

输出:

(((((1*2)*3)*4)*5)*(1*2))
(1*(2*(3*(4*(5*(1*2))))))

请注意，除了最外部的 Transform 调用外，还必须对每个子表达式应用 Transform 函数(请参阅最后一个 Transform过载)。

可以找到完整的源代码here .

最佳答案

虽然 OP 想要一个不使用 Boost.Proto 的解决方案，但其他人可能有兴趣看看如何(非常容易地)使用它来完成:

#include <iostream>
#include <boost/type_traits/is_same.hpp>
#include <boost/proto/proto.hpp>

namespace proto = boost::proto;
using proto::_;

struct empty {};

struct transform
  : proto::reverse_fold_tree<
        _
      , empty()
      , proto::if_<
            boost::is_same<proto::_state, empty>()
          , _
          , proto::_make_multiplies(_, proto::_state)
        >
    >
{};

int main()
{
    proto::literal<int> a(1), b(2), c(3), d(4);
    proto::display_expr( a * b * c * d );
    proto::display_expr( transform()(a * b * c * d) );
}

上面的代码显示:

multiplies(
    multiplies(
        multiplies(
            terminal(1)
          , terminal(2)
        )
      , terminal(3)
    )
  , terminal(4)
)
multiplies(
    terminal(1)
  , multiplies(
        terminal(2)
      , multiplies(
            terminal(3)
          , terminal(4)
        )
    )
)

关于c++ - 转换表达式模板树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18213249/