표현식 템플릿 트리 변환

Question

표현식 템플릿 트리가 주어지면이를 처리하기 전에 새로운 최적화 된 트리를 만들고 싶습니다. 곱셈 연산의 다음과 같은 예를 생각해

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

내가 변형 된 표현을 생산하는 싶습니다 때문에 operator*의 왼쪽에서 오른쪽으로 연관성, 표현 트리에, 생산

a * b * c * d, 

곱셈에서 발생하는 트리 오른쪽에서 왼쪽으로 :

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

이진 표현 유형을 고려

의해 정의된다

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

:

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

및 lvalues로 구성 될 때 CONST 좌변 - 참조와 하위 표현식을 보장하기 위해 사용되며, rvalues로 구성 될 때 rvalues를 복사 (복사/이동)합니다.

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)를 해결하기 위해이를 적용하는 방법을 모르겠어요.

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

3)이 문제에 대한 청소기 해결책은 있는가 :

2) 어떻게 재귀 라인을 작성하려면 어떻게해야합니까?

---

편집 :는 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; 
} 

출력 : 대부분의 외장 Transform 통화 이외의 모든 하위 표현에 Transform 기능을 적용 할 필요하다고

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

참고 (을 참조 아래에 그의 대답에 내 전체 솔루션을 기반으로 마지막으로 Transform 과부하).

전체 소스 코드는 here입니다.완벽한 전달을 통합하지 않고

Answer 1

:

#include <iostream> 

// simplified by making it an aggregate 
template<typename Left, typename Right> 
struct BinaryTimesExpr 
{ 
    Left left; 
    Right right; 
}; 

// "debug"/demo output 
template<typename Left, typename Right> 
std::ostream& operator<<(std::ostream& o, BinaryTimesExpr<Left, Right> const& p) 
{ 
    o << "(" << p.left << "*" << p.right << ")"; 
    return o; 
} 

// NOTE: removed reference as universal-ref yields a reference type for lvalues! 
template<typename Left, typename Right> 
BinaryTimesExpr < typename std::remove_reference<Left>::type, 
        typename std::remove_reference<Right>::type > 
operator*(Left&& l, Right&& r) 
{ 
    return {std::forward<Left>(l), std::forward<Right>(r)}; 
} 


// overload to end recursion (no-op) 
template<typename Expr> 
auto Transform(const Expr& expr) -> Expr 
{ 
    return expr; 
} 

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


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

출력 :

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

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

Answer 2

표현은 정말 이진 트리입니다.

예를 들어, 표현 a * b * c * d * e 그래서 당신이해야하는 것은 (세 살 아이 같은 도면에 대한 죄송합니다, 스타일러스없이 아이 패드 ...)를 folowwing 나무는 ((((a * b) * c) * d) * e)로 평가 보다시피, 기본 평가 식은 왼쪽 첫 번째 inorder으로 트리를 trasversing하여 생성됩니다.

한편

에게, 역 평가 식 (원하는 무엇 OP) 오른쪽 - 첫 중위로 트리를 trasversing 생성됩니다

이

그래서 하나 개의 솔루션이 trasverse하는 것입니다 생성 된 표현 트리를 오른쪽 첫번째 우선 순위으로 만들고 프로세스에서 새 트리를 만듭니다.

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

위의 코드 표시 : 영업 이익은 Boost.Proto을 사용하지 않은 솔루션을 원하지만

Answer 3

, 다른 사람을 사용하여 수행이 (아주 쉽게) 할 수있는 방법을보고 관심이있을 수도 있습니다

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