API tools faq
paste
Advertisement
Dukales

fold constant subexpressions

Dukales
Oct 12th, 2013
2,787
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 26.58 KB | None | 0 0
raw download clone embed print report
  1. #!/usr/bin/env bash -vex
  2.  
  3. # C++14 implementation of constant subexpression folding algorithm
  4. #
  5. # Copyright (c) 2013-2014, Anatoliy V. Tomilov
  6. # All rights reserved.
  7. #
  8. # Redistribution and use in source and binary forms, with or without
  9. # modification, are permitted provided that the following condition is met:
  10. # Redistributions of source code must retain the above copyright notice, this condition and the following disclaimer.
  11. #
  12. # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  13. # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  14. # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  15. # ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  16. # LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  17. # CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  18. # SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  19. # INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  20. # CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  21. # ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  22. # POSSIBILITY OF SUCH DAMAGE.
  23. #
  24.  
  25. # cls ; bash self.bash 2>&1 | tee self.log | less
  26. WARN="-W -Wall -Wextra -Werror"
  27. INCLUDE="-I/c/libs/boost-trunk"
  28. g++ -x c++ - -std=gnu++1y $WARN $INCLUDE -Og -g -o a <<__EOF && ./a && echo -e "\e[1;32msucceeded\e[0m" || echo -e "\e[1;31mfailed\e[0m"
  29. #include <boost/variant.hpp>
  30. #include <boost/variant/recursive_variant.hpp>
  31. #include <boost/fusion/include/adapt_struct.hpp>
  32. #include <boost/mpl/distance.hpp>
  33. #include <boost/mpl/begin.hpp>
  34. #include <boost/mpl/find.hpp>
  35.  
  36. #include <iostream>
  37. #include <string>
  38. #include <deque>
  39. #include <stack>
  40. #include <iterator>
  41. #include <stdexcept>
  42. #include <type_traits>
  43. #include <functional>
  44. #include <utility>
  45.  
  46. #include <cstdlib>
  47. #include <cstddef>
  48. #include <cmath>
  49.  
  50. using size_type = std::size_t;
  51. using symbol_type = std::string;
  52.  
  53. template< typename V, typename T >
  54. using variant_index = boost::mpl::distance< typename boost::mpl::begin< typename V::types >::type, typename boost::mpl::find< typename V::types, T >::type >;
  55.  
  56. enum class binary { add, sub, mul, div, mod, pow };
  57.  
  58. inline
  59. size_type
  60. precedence(binary const _op)
  61. {
  62.     switch (_op) {
  63.     case binary::add :
  64.     case binary::sub : {
  65.         return 2;
  66.     }
  67.     case binary::mul :
  68.     case binary::div :
  69.     case binary::mod : {
  70.         return 3;
  71.     }
  72.     case binary::pow : {
  73.         return 4;
  74.     }
  75.     default : {
  76.         break;
  77.     }
  78.     }
  79.     throw std::logic_error("unsupported operator");
  80. }
  81.  
  82. inline
  83. std::ostream & operator << (std::ostream & out, binary const _op)
  84. {
  85.     switch (_op) {
  86.     case binary::add : return out << " + ";
  87.     case binary::sub : return out << " - ";
  88.     case binary::mul : return out << " * ";
  89.     case binary::div : return out << " / ";
  90.     case binary::mod : return out << " % ";
  91.     case binary::pow : return out << " ^ ";
  92.     default : {
  93.         break;
  94.     }
  95.     }
  96.     throw std::logic_error("unsupported operator");
  97. }
  98.  
  99. template< typename ...T >
  100. struct extended_variant
  101. {
  102.  
  103.     struct adapted_variant_tag;
  104.  
  105.     using base_type = extended_variant;
  106.     using variant_type = boost::variant< T... >;
  107.     using types = typename variant_type::types;
  108.  
  109.     template< typename X >
  110.     using index = variant_index< variant_type, X >;
  111.  
  112.     extended_variant() = default;
  113.  
  114.     extended_variant(extended_variant const &) = default;
  115.     extended_variant(extended_variant &) = default;
  116.     extended_variant(extended_variant &&) = default;
  117.  
  118.     extended_variant & operator = (extended_variant const &) = default;
  119.     extended_variant & operator = (extended_variant &) = default;
  120.     extended_variant & operator = (extended_variant &&) = default;
  121.  
  122.     template< typename X >
  123.     extended_variant(X && _value)
  124.         : variant_(std::forward< X >(_value))
  125.     { ; }
  126.  
  127.     template< typename X >
  128.     extended_variant &
  129.     operator = (X && _value)
  130.     {
  131.         variant_ = std::forward< X >(_value);
  132.         return *this;
  133.     }
  134.  
  135.     template< typename Visitor >
  136.     typename Visitor::result_type
  137.     apply_visitor(Visitor & _visitor)
  138.     {
  139.         return variant_.apply_visitor(_visitor);
  140.     }
  141.  
  142.     template< typename Visitor >
  143.     typename Visitor::result_type
  144.     apply_visitor(Visitor & _visitor) const
  145.     {
  146.         return variant_.apply_visitor(_visitor);
  147.     }
  148.  
  149.     variant_type &
  150.     get()
  151.     {
  152.         return variant_;
  153.     }
  154.  
  155.     variant_type const &
  156.     get() const
  157.     {
  158.         return variant_;
  159.     }
  160.  
  161. private :
  162.  
  163.     variant_type variant_;
  164.  
  165. };
  166.  
  167. namespace boost
  168. {
  169.  
  170. template< typename X, typename ...T >
  171. X const &
  172. get(extended_variant< T... > const & _extended_variant)
  173. {
  174.     return boost::get< X >(_extended_variant.get());
  175. }
  176.  
  177. template< typename X, typename ...T >
  178. X &
  179. get(extended_variant< T... > & _extended_variant)
  180. {
  181.     return boost::get< X >(_extended_variant.get());
  182. }
  183.  
  184. template< typename X, typename ...T >
  185. X const *
  186. get(extended_variant< T... > const * _extended_variant)
  187. {
  188.     return boost::get< X >(std::addressof(_extended_variant->get()));
  189. }
  190.  
  191. template< typename X, typename ...T >
  192. X *
  193. get(extended_variant< T... > * _extended_variant)
  194. {
  195.     return boost::get< X >(std::addressof(_extended_variant->get()));
  196. }
  197.  
  198. } // namespace boost
  199.  
  200. namespace ast
  201. {
  202.  
  203. using identifier = symbol_type;
  204.  
  205. template< typename G >
  206. struct expression;
  207.  
  208. template< typename G >
  209. struct binary_expression;
  210.  
  211. template< typename G >
  212. struct operand;
  213.  
  214. template< typename G >
  215. using operand_cref = std::reference_wrapper< operand< G > const >;
  216.  
  217. template< typename G >
  218. struct operand
  219.         : extended_variant<
  220.         boost::blank,
  221.         G,
  222.         identifier,
  223.         boost::recursive_wrapper< expression< G > >,
  224.         boost::recursive_wrapper< binary_expression< G > >,
  225.         operand_cref< G >
  226.         >
  227. {
  228.  
  229.     operand() = default;
  230.  
  231.     operand(operand const &) = default;
  232.     operand(operand &) = default;
  233.     operand(operand &&) = default;
  234.  
  235.     using operand::base_type::base_type;
  236.  
  237.     operand & operator = (operand const &) = default;
  238.     operand & operator = (operand &) = default;
  239.     operand & operator = (operand &&) = default;
  240.  
  241.     template< typename X >
  242.     operand &
  243.     operator = (X && _value)
  244.     {
  245.         operand::base_type::get() = std::forward< X >(_value);
  246.         return *this;
  247.     }
  248.  
  249.     friend
  250.     inline
  251.     std::ostream & operator << (std::ostream & out, operand const & _operand)
  252.     {
  253.         switch (_operand.get().which()) {
  254.         case operand::base_type::template index< binary_expression< G > >::value :
  255.         case operand::base_type::template index< expression< G > >::value : {
  256.             return out << '(' << _operand.get() << ')';
  257.         }
  258.         default : {
  259.             break;
  260.         }
  261.         }
  262.         return out << _operand.get();
  263.     }
  264.  
  265. };
  266.  
  267. template< typename G >
  268. struct operation
  269. {
  270.  
  271.     binary operator_;
  272.     operand< G > operand_;
  273.  
  274.     friend
  275.     inline
  276.     std::ostream & operator << (std::ostream & out, operation const & _operation)
  277.     {
  278.         return out << _operation.operator_
  279.                    << _operation.operand_;
  280.     }
  281.  
  282. };
  283.  
  284. template< typename G >
  285. using operation_list = std::deque< operation< G > >;
  286.  
  287. template< typename G >
  288. struct expression
  289. {
  290.  
  291.     operand< G > first_;
  292.     operation_list< G > rest_;
  293.  
  294.     friend
  295.     inline
  296.     std::ostream & operator << (std::ostream & out, expression const & _expression)
  297.     {
  298.         out << _expression.first_;
  299.         for (operation< G > const & operation_ : _expression.rest_) {
  300.             out << operation_;
  301.         }
  302.         return out;
  303.     }
  304.  
  305. };
  306.  
  307. template< typename G >
  308. struct binary_expression
  309. {
  310.  
  311.     operand< G > lhs_;
  312.     binary operator_;
  313.     operand< G > rhs_;
  314.  
  315.     friend
  316.     inline
  317.     std::ostream & operator << (std::ostream & out, binary_expression const & _ast)
  318.     {
  319.         return out << _ast.lhs_ << _ast.operator_ << _ast.rhs_;
  320.     }
  321.  
  322. };
  323.  
  324. } // namespace ast
  325.  
  326. namespace std
  327. {
  328.  
  329. template< typename G >
  330. ast::operand_cref< G >
  331. cref(ast::operand< G > const & _operand)
  332. {
  333.     if (_operand.get().which() == ast::operand< G >::template index< ast::operand_cref< G > >::value) {
  334.         return boost::get< ast::operand_cref< G > >(_operand);
  335.     }
  336.     return _operand;
  337. }
  338.  
  339. } // namespace std
  340.  
  341. #if 0
  342. // unused
  343. BOOST_FUSION_ADAPT_TPL_STRUCT(
  344.         (G),
  345.         (ast::operation)(G),
  346.         (binary, operator_)
  347.         (ast::operand< G >, operand_)
  348.         )
  349.  
  350. BOOST_FUSION_ADAPT_TPL_STRUCT(
  351.         (G),
  352.         (ast::expression)(G),
  353.         (ast::operand< G >, first_)
  354.         (ast::operation_list< G >, rest_)
  355.         )
  356. #endif
  357.  
  358. template< typename G, typename D >
  359. struct shunting_yard_algorithm
  360.     : boost::static_visitor< typename D::result_type >
  361. {
  362.  
  363.     static_assert(!std::is_reference< D >::value,
  364.                   "!");
  365.  
  366.     using typename boost::static_visitor< typename D::result_type >::result_type;
  367.  
  368.     shunting_yard_algorithm(D & _dispatcher)
  369.         : dispatcher_(_dispatcher)
  370.     { ; }
  371.  
  372.     result_type
  373.     traverse(ast::expression< G > const & _expression);
  374.  
  375.     struct lhs_op_rhs
  376.     {
  377.  
  378.         size_type const lhs_;
  379.         binary    const op_;
  380.         size_type const rhs_;
  381.  
  382.     };
  383.  
  384.     using operand_cref_type = ast::operand_cref< G >;
  385.     using node_type = boost::variant< lhs_op_rhs, operand_cref_type >;
  386.  
  387.     result_type
  388.     operator () (node_type const & _node) const
  389.     {
  390.         return boost::apply_visitor(*this, _node);
  391.     }
  392.  
  393.     result_type
  394.     operator () (lhs_op_rhs const & _top) const
  395.     { // dispatcher can perform a tree balancing here
  396.         return dispatcher_(output_.at(_top.lhs_), _top.op_, output_.at(_top.rhs_));
  397.     }
  398.  
  399.     result_type
  400.     operator () (operand_cref_type const & _top) const
  401.     {
  402.         return dispatcher_(_top.get());
  403.     }
  404.  
  405. private :
  406.  
  407.     D & dispatcher_;
  408.  
  409.     std::deque< node_type > output_;
  410.  
  411.     struct lhs_op
  412.     {
  413.  
  414.         size_type const lhs_;
  415.         binary    const op_;
  416.  
  417.     };
  418.  
  419. };
  420.  
  421. template< typename G, typename D >
  422. auto
  423. shunting_yard_algorithm< G, D >::traverse(ast::expression< G > const & _input)
  424. -> result_type
  425. {
  426.     BOOST_ASSERT(output_.empty());
  427.     if (_input.rest_.empty()) {
  428.         return dispatcher_(_input.first_);
  429.     }
  430.     if (_input.rest_.size() == 1) {
  431.         ast::operation< G > const & operation_ = _input.rest_.back();
  432.         return dispatcher_(_input.first_, operation_.operator_, operation_.operand_);
  433.     }
  434.     //output_.reserve(_input.rest_.size() * 2 + 1); // total number of operators and operands, but we needs push_front()
  435.     std::stack< lhs_op > lhs_op_;
  436.     for (ast::operation< G > const & operation_ : _input.rest_) {
  437.         if (!lhs_op_.empty()) {
  438.             size_type const p_ = precedence(operation_.operator_);
  439.             do {
  440.                 lhs_op const & top_ = lhs_op_.top();
  441.                 if (precedence(top_.op_) < p_) {
  442.                     break;
  443.                 }
  444.                 output_.emplace_back(lhs_op_rhs{top_.lhs_, top_.op_, output_.size()});
  445.                 lhs_op_.pop();
  446.             } while (!lhs_op_.empty());
  447.         }
  448.         lhs_op_.emplace(lhs_op{output_.size(), operation_.operator_});
  449.         output_.emplace_back(operation_.operand_);
  450.     }
  451.     while (!lhs_op_.empty()) {
  452.         lhs_op const & top_ = lhs_op_.top();
  453.         output_.emplace_back(lhs_op_rhs{top_.lhs_, top_.op_, output_.size()});
  454.         lhs_op_.pop();
  455.     }
  456.     output_.emplace_front(_input.first_);
  457.     return operator () (output_.back());
  458. }
  459.  
  460. template< typename G >
  461. struct expression_evaluator
  462.         : boost::static_visitor< ast::operand< G > >
  463. {
  464.  
  465.     using typename boost::static_visitor< ast::operand< G > >::result_type;
  466.  
  467.     template< typename ...T >
  468.     result_type
  469.     operator () (T &&... _ast) const
  470.     {
  471.         return evaluate(std::forward< T >(_ast)...);
  472.     }
  473.  
  474. private :
  475.  
  476.     using identifier_type        = ast::identifier;
  477.     using operation_type         = ast::operation< G >;
  478.     using expression_type        = ast::expression< G >;
  479.     using binary_expression_type = ast::binary_expression< G >;
  480.     using operand_cref_type      = ast::operand_cref< G >;
  481.     using operand_type           = ast::operand< G >;
  482.    
  483.     result_type
  484.     evaluate(boost::blank const &) const
  485.     {
  486.         return {};
  487.     }
  488.  
  489.     result_type
  490.     evaluate(G const & _ast) const
  491.     {
  492.         return _ast;
  493.     }
  494.  
  495.     result_type
  496.     evaluate(identifier_type const & _ast) const
  497.     {
  498.         return _ast;
  499.     }
  500.  
  501.     struct operation_commutator
  502.             : boost::static_visitor< result_type >
  503.     {
  504.  
  505.         constexpr
  506.         operation_commutator(binary const _op)
  507.             : op_(_op)
  508.         { ; }
  509.  
  510.         result_type
  511.         operator () (operand_type && _lhs, operand_type && _rhs) const
  512.         {
  513.             return boost::apply_visitor(*this, _lhs.get(), _rhs.get());
  514.         }
  515.  
  516.         template< typename L, typename R >
  517.         result_type
  518.         operator () (L & _lhs, R & _rhs) const
  519.         {
  520.             return binary_expression_type{std::move(_lhs), op_, std::move(_rhs)};
  521.         }
  522.  
  523.         template< typename L >
  524.         result_type
  525.         operator () (L & _lhs, G & _rhs) const
  526.         {
  527. #pragma GCC diagnostic push
  528. #pragma GCC diagnostic ignored "-Wfloat-equal"
  529.             switch (op_) {
  530.             case binary::add :
  531.             case binary::sub : {
  532.                 if (_rhs == G(0.0L)) {
  533.                     return std::move(_lhs);
  534.                 }
  535.                 break;
  536.             }
  537.             case binary::mul : {
  538.                 if (_rhs == G(0.0L)) {
  539.                     return G(0.0L);
  540.                 } else if (_rhs == G(1.0L)) {
  541.                     return std::move(_lhs);
  542.                 }
  543.                 break;
  544.             }
  545.             case binary::div : {
  546.                 if (_rhs == G(1.0L)) {
  547.                     return std::move(_lhs);
  548.                 } else if (_rhs == G(0.0L)) {
  549.                     throw std::runtime_error("domain error: / division by zero");
  550.                 }
  551.                 break;
  552.             }
  553.             case binary::mod : {
  554.                 if (_rhs == G(0.0L)) {
  555.                     throw std::runtime_error("domain error: % division by zero");
  556.                 }
  557.                 break;
  558.             }
  559.             case binary::pow : {
  560.                 if (_rhs == G(0.0L)) {
  561.                     return G(1.0L);
  562.                 } else if (_rhs == G(1.0L)) {
  563.                     return std::move(_lhs);
  564.                 }
  565.                 break;
  566.             }
  567.             default : {
  568.                 throw std::logic_error("unsupported operator");
  569.             }
  570.             }
  571. #pragma GCC diagnostic pop
  572.             return binary_expression_type{std::move(_lhs), op_, std::move(_rhs)};
  573.         }
  574.  
  575.         template< typename R >
  576.         result_type
  577.         operator () (G & _lhs, R & _rhs) const
  578.         {
  579. #pragma GCC diagnostic push
  580. #pragma GCC diagnostic ignored "-Wfloat-equal"
  581.             switch (op_) {
  582.             case binary::add : {
  583.                 if (_lhs == G(0.0L)) {
  584.                     return std::move(_rhs);
  585.                 }
  586.                 break;
  587.             }
  588.             case binary::sub : {
  589.                 break;
  590.             }
  591.             case binary::mul : {
  592.                 if (_lhs == G(0.0L)) {
  593.                     return G(0.0L);
  594.                 } else if (_lhs == G(1.0L)) {
  595.                     return std::move(_rhs);
  596.                 }
  597.                 break;
  598.             }
  599.             case binary::div : {
  600.                 if (_lhs == G(0.0L)) {
  601.                     return G(0.0L);
  602.                 }
  603.                 break;
  604.             }
  605.             case binary::mod : {
  606.                 if (_lhs == G(0.0L)) {
  607.                     return G(0.0L);
  608.                 }
  609.                 break;
  610.             }
  611.             case binary::pow : {
  612.                 if (_lhs == G(1.0L)) {
  613.                     return G(1.0L);
  614.                 }
  615.                 break;
  616.             }
  617.             default : {
  618.                 throw std::logic_error("unsupported operator");
  619.             }
  620.             }
  621. #pragma GCC diagnostic pop
  622.             return binary_expression_type{std::move(_lhs), op_, std::move(_rhs)};
  623.         }
  624.  
  625.         result_type
  626.         operator () (G & _lhs, G & _rhs) const;
  627.  
  628.     private :
  629.  
  630.         binary const op_;
  631.  
  632.     };
  633.  
  634.     operation_commutator const add_{binary::add};
  635.     operation_commutator const sub_{binary::sub};
  636.     operation_commutator const mul_{binary::mul};
  637.     operation_commutator const div_{binary::div};
  638.     operation_commutator const mod_{binary::mod};
  639.     operation_commutator const pow_{binary::pow};
  640.  
  641.     result_type
  642.     evaluate(operand_type && _lhs, binary const _op, operand_type && _rhs) const
  643.     {
  644.         switch (_op) {
  645.         case binary::add   : {
  646.             return add_(std::move(_lhs), std::move(_rhs));
  647.         }
  648.         case binary::sub  : {
  649.             return sub_(std::move(_lhs), std::move(_rhs));
  650.         }
  651.         case binary::mul  : {
  652.             return mul_(std::move(_lhs), std::move(_rhs));
  653.         }
  654.         case binary::div : {
  655.             return div_(std::move(_lhs), std::move(_rhs));
  656.         }
  657.         case binary::mod : {
  658.             return mod_(std::move(_lhs), std::move(_rhs));
  659.         }
  660.         case binary::pow : {
  661.             return pow_(std::move(_lhs), std::move(_rhs));
  662.         }
  663.         default : {
  664.             break;
  665.         }
  666.         }
  667.         throw std::logic_error("unsupported operator");
  668.     }
  669.  
  670.     result_type
  671.     evaluate(binary_expression_type const & _ast) const
  672.     {
  673.         return operator () (operator () (_ast.lhs_),
  674.                             _ast.operator_,
  675.                             operator () (_ast.rhs_));
  676.     }
  677.  
  678.     struct tree_switch
  679.             : boost::static_visitor< result_type >
  680.     {
  681.  
  682.         using shunting_yard_algorithm_type = shunting_yard_algorithm< G, tree_switch const >;
  683.         using node_type = typename shunting_yard_algorithm_type::node_type;
  684.  
  685.         tree_switch(expression_evaluator const & _evaluate_expression)
  686.             : evaluate_expression_(_evaluate_expression)
  687.             , _(*this)
  688.         { ; }
  689.  
  690.         result_type
  691.         traverse(expression_type const & _expression)
  692.         {
  693.             return _.traverse(_expression);
  694.         }
  695.  
  696.         result_type
  697.         operator () (operand_type const & _ast) const
  698.         {
  699.             return evaluate_expression_(_ast);
  700.         }
  701.  
  702.         result_type
  703.         operator () (node_type const & _lhs, binary const _op, node_type const & _rhs) const
  704.         {
  705.             return evaluate_expression_(_(_lhs).get(), _op, _(_rhs).get());
  706.         }
  707.  
  708.     private :
  709.  
  710.         expression_evaluator const & evaluate_expression_;
  711.         shunting_yard_algorithm_type _;
  712.  
  713.     };
  714.  
  715.     result_type
  716.     evaluate(expression_type const & _expression) const
  717.     {
  718.         if (_expression.rest_.empty()) {
  719.             return operator () (_expression.first_);
  720.         } else if (_expression.rest_.size() == 1) {
  721.             operation_type const & op_rhs_ = _expression.rest_.back();
  722.             return operator () (operator () (_expression.first_),
  723.                                 op_rhs_.operator_,
  724.                                 operator () (op_rhs_.operand_));
  725.         } else {
  726.             tree_switch Dijkstra(*this);
  727.             return Dijkstra.traverse(_expression);
  728.         }
  729.     }
  730.  
  731.     result_type
  732.     evaluate(operand_type const & _ast) const
  733.     {
  734.         return boost::apply_visitor(*this, _ast.get());
  735.     }
  736.  
  737.     result_type
  738.     evaluate(operand_cref_type const & _ast) const
  739.     {
  740.         return operator () (_ast.get());
  741.     }
  742.  
  743. };
  744.  
  745. template< typename G >
  746. inline G pow(G const & _x, G const & _y);
  747. template< typename G >
  748. inline G fmod(G const & _x, G const & _y);
  749.  
  750. template< typename G >
  751. auto
  752. expression_evaluator< G >::operation_commutator::operator () (G & _lhs, G & _rhs) const
  753. -> result_type
  754. {
  755. #pragma GCC diagnostic push
  756. #pragma GCC diagnostic ignored "-Wfloat-equal"
  757.     switch (op_) {
  758.     case binary::add : {
  759.         return _lhs + _rhs;
  760.     }
  761.     case binary::sub : {
  762.         return _lhs - _rhs;
  763.     }
  764.     case binary::mul : {
  765.         return _lhs * _rhs;
  766.     }
  767.     case binary::div : {
  768.         if (_rhs == G(0.0L)) {
  769.             throw std::runtime_error("domain error: / division by zero");
  770.         }
  771.         return _lhs / _rhs;
  772.     }
  773.     case binary::mod : {
  774.         if (_rhs == G(0.0L)) {
  775.             throw std::runtime_error("domain error: % division by zero");
  776.         }
  777.         return fmod<>(_lhs, _rhs);
  778.     }
  779.     case binary::pow : {
  780.         if (_lhs == G(0.0L)) {
  781.             if (G(0.0L) < _rhs) {
  782.                 return G(0.0L);
  783.             } else {
  784.                 throw std::runtime_error("domain error: ^ base is 0 and exp is less than or equal to ​0");
  785.             }
  786.         } else if (_lhs < G(0.0L)) {
  787.             if (!(fmod<>(_rhs, G(1.0L)) == G(0.0L))) {
  788.                 throw std::runtime_error("domain error: ^ base is negative and exp is not an integer value");
  789.             }
  790.         }
  791.         if (_rhs == G(0.0L)) {
  792.             return G(1.0L);
  793.         } else if (_rhs == G(1.0L)) {
  794.             return _lhs;
  795.         }
  796.         return pow<>(_lhs, _rhs);
  797.     }
  798.     default : {
  799.         break;
  800.     }
  801.     }
  802. #pragma GCC diagnostic pop
  803.     throw std::logic_error("unsupported operator");
  804. }
  805.  
  806. template< typename G >
  807. struct test
  808. {
  809.  
  810.     using operand_type           = ast::operand< G >;
  811.     using expression_type        = ast::expression< G >;
  812.     using binary_expression_type = ast::binary_expression< G >;
  813.  
  814.     test(std::ostream & _out)
  815.         : out(_out)
  816.         , expression_evaluator_()
  817.     { ; }
  818.  
  819.     void
  820.     operator () () const
  821.     {
  822. #pragma GCC diagnostic push
  823. #pragma GCC diagnostic ignored "-Wmissing-field-initializers"
  824.         operand_type const x{
  825.             "x"
  826.         };
  827.         expression_type const e0{
  828.             x
  829.         };
  830.         print(e0);
  831.         expression_type const e1{
  832.             e0,
  833.             {
  834.                 {binary::add, G(1.0L)}
  835.             }
  836.         };
  837.         print(e1);
  838.         expression_type const e2{
  839.             G(2.0L),
  840.             {
  841.                 {binary::pow, G(3.0L)}
  842.             }
  843.         };
  844.         print(e2);
  845.         expression_type const e3{
  846.             expression_type{
  847.                 expression_type{
  848.                     expression_type{
  849.                         expression_type{
  850.                             G(3.0L)
  851.                         }
  852.                     }
  853.                 }
  854.             }
  855.         };
  856.         print(e3);
  857.         expression_type const e4{
  858.             e2,
  859.             {
  860.                 {binary::add, G(3.0L)},
  861.                 {binary::div, G(1.5L)}
  862.             }
  863.         };
  864.         print(e4);
  865.         expression_type const e5{
  866.             expression_type{
  867.                 e0,
  868.                 {
  869.                     {binary::sub, e2}
  870.                 }
  871.             },
  872.             {
  873.                 {binary::mul, e4}
  874.             }
  875.         };
  876.         print(e5);
  877.         expression_type const e6{
  878.             "x",
  879.             {
  880.                 {binary::mul, "y"},
  881.                 {binary::add, "z"},
  882.                 {binary::div, "t"},
  883.                 {binary::sub, "u"},
  884.                 {binary::mul, "v"},
  885.                 {binary::pow, "w"}
  886.             }
  887.         };
  888.         print(e6);
  889.         expression_type const e7{
  890.             G(2.0L),
  891.             {
  892.                 {binary::mul, G(3.0L)},
  893.                 {binary::add, G(10.0L)},
  894.                 {binary::div, G(2.0L)},
  895.                 {binary::sub, G(7.0L)},
  896.                 {binary::mul, G(2.0L)},
  897.                 {binary::pow, G(3.0L)}
  898.             }
  899.         };
  900.         print(e7);
  901.         expression_type const e8{
  902.             G(2.0L),
  903.             {
  904.                 {binary::mul, "a"},
  905.                 {binary::add, G(10.0L)},
  906.                 {binary::div, "b"},
  907.                 {binary::sub, G(7.0L)},
  908.                 {binary::mul, "c"},
  909.                 {binary::pow, G(3.0L)}
  910.             }
  911.         };
  912.         print(e8);
  913.         expression_type const e9{
  914.             "first",
  915.             {
  916.                 {binary::sub, G(3.0L)},
  917.                 {binary::add, G(10.0L)},
  918.                 {binary::sub, G(2.0L)},
  919.                 {binary::add, G(7.0L)},
  920.                 {binary::sub, G(2.0L)},
  921.                 {binary::add, G(3.0L)}
  922.             }
  923.         };
  924.         print(e9);
  925.         expression_type const e10{
  926.             G(2.0L),
  927.             {
  928.                 {binary::sub, G(3.0L)},
  929.                 {binary::add, G(10.0L)},
  930.                 {binary::sub, G(2.0L)},
  931.                 {binary::add, G(7.0L)},
  932.                 {binary::sub, G(2.0L)},
  933.                 {binary::add, "last"}
  934.             }
  935.         };
  936.         print(e10);
  937.         expression_type const e11{
  938.             G(2.0L),
  939.             {
  940.                 {binary::div, G(0.0L)}
  941.             }
  942.         };
  943.         print(e11);
  944.         expression_type const e12{
  945.             G(-1.0L),
  946.             {
  947.                 {binary::pow, G(1.1L)}
  948.             }
  949.         };
  950.         print(e12);
  951. #pragma GCC diagnostic pop
  952.     }
  953.  
  954. private :
  955.  
  956.     std::ostream & out;
  957.     expression_evaluator< G > const expression_evaluator_;
  958.  
  959.     void
  960.     print(expression_type const & _expression) const
  961.     {
  962.         try {
  963.             out << _expression << std::flush
  964.                 << " -> "
  965.                 << expression_evaluator_(_expression)
  966.                 << std::endl;
  967.         } catch (std::runtime_error const & _re) {
  968.             std::cerr << _re.what() << std::endl;
  969.         }
  970.     }
  971.  
  972. };
  973.  
  974. using G = double;
  975.  
  976. template<>
  977. inline
  978. G
  979. pow<>(G const & _x, G const & _y)
  980. { return std::pow(_x, _y); }
  981.  
  982. template<>
  983. inline
  984. G
  985. fmod<>(G const & _x, G const & _y)
  986. { return std::fmod(_x, _y); }
  987.  
  988. int main()
  989. {
  990.     test< G > const test_ = std::cout;
  991.     test_();
  992.     return EXIT_SUCCESS;
  993. }
  994. /*
  995. x -> x
  996. (x) + 1 -> (x + 1)
  997. 2 ^ 3 -> 8
  998. ((((3)))) -> 3
  999. (2 ^ 3) + 3 / 1.5 -> 10
  1000. ((x) - (2 ^ 3)) * ((2 ^ 3) + 3 / 1.5) -> ((x - 8) * 10)
  1001. x * y + z / t - u * v ^ w -> (((x * y) + (z / t)) - (u * (v ^ w)))
  1002. 2 * 3 + 10 / 2 - 7 * 2 ^ 3 -> -45
  1003. 2 * a + 10 / b - 7 * c ^ 3 -> (((2 * a) + (10 / b)) - (7 * (c ^ 3)))
  1004. first - 3 + 10 - 2 + 7 - 2 + 3 -> ((((((first - 3) + 10) - 2) + 7) - 2) + 3)
  1005. 2 - 3 + 10 - 2 + 7 - 2 + last -> (12 + last)
  1006. domain error: / division by zero
  1007. domain error: ^ base is negative and exp is not an integer value
  1008. */
  1009. __EOF
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!