Advertisement
Guest User

Untitled

a guest
Dec 27th, 2014
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.46 KB | None | 0 0
  1. /*
  2.  * this cpp code is written from some Rust code: http://pastebin.com/aYDTc7PL
  3.  * the code tries to do basic calculation without any kind of compiler theory
  4.  */
  5.  
  6. #include <memory>
  7. #include <vector>
  8. #include <cassert>
  9. #include <iostream>
  10. #include <string>
  11. #include <sstream>
  12. #include <exception>
  13. /*
  14.  *  we need a tree to represent the calculation
  15.  */
  16. template<typename T>
  17. class Node{
  18.     Node(Node&) = delete;
  19.     Node(Node&&) = delete;
  20.     Node operator=(Node&) = delete;
  21.     Node operator=(Node&&) = delete;
  22.     T value;
  23. public:
  24.     T get()const{
  25.         return value;
  26.     }
  27.     Node(T v) :value(v){}
  28.     virtual ~Node(){}
  29. };
  30. template<typename T>
  31. class NodeWithChildren :public Node<T>{
  32.     std::shared_ptr<Node<T>> left, right;
  33. public:
  34.     using Node<T>::get;
  35.     NodeWithChildren(T v, std::shared_ptr<Node<T>> left, std::shared_ptr<Node<T>> right) :
  36.         Node<T>(v), left(left), right(right){}
  37.     std::shared_ptr<Node<T>> get_left()const{
  38.         return left;
  39.     }
  40.     std::shared_ptr<Node<T>> get_right()const{
  41.         return right;
  42.     }
  43. };
  44. template<typename T>
  45. using TreeList = std::vector<std::shared_ptr<Node<T>>>;
  46. template<typename T>
  47. std::shared_ptr<Node<T>> make_leaf(T v){
  48.     return std::make_shared<Node<T>>(v);
  49. }
  50. template<typename T>
  51. std::shared_ptr<Node<T>> make_tree(T v, std::shared_ptr<Node<T>> left, std::shared_ptr<Node<T>> right){
  52.     return std::make_shared<NodeWithChildren<T>>(v, left, right);
  53. }
  54. // it is kinda like partition, the operation can make (`a`, `+`, `b`) from `+` and (`a`, `b`)
  55. template<typename T>
  56. TreeList<T> make_trees(T v, TreeList<T> lhs, TreeList<T> rhs){
  57.     TreeList<T> ret;
  58.     for (auto& i : lhs){
  59.         for (auto& j : rhs){
  60.             ret.push_back(make_tree(v, i, j));
  61.         }
  62.     }
  63.     return ret;
  64. }
  65. // insert elements form a vector to a complete-binary-tree in order
  66. template<typename T>
  67. TreeList<T> make_possible_trees(std::vector<T> const& stack){
  68.     auto size = stack.size();
  69.     assert(size % 2 == 1);
  70.     TreeList<T> ret;
  71.     if (size == 1){
  72.         ret.push_back(make_leaf(stack[0]));
  73.         return ret;
  74.     }
  75.     for (auto i = 1u; i < size; i += 2){
  76.         TreeList<T> lefts = make_possible_trees(std::vector<T>(stack.begin(), stack.begin() + i));
  77.         TreeList<T> rights = make_possible_trees(std::vector<T>(stack.begin() + i + 1, stack.end()));
  78.         TreeList<T> trees = make_trees<T>(stack[i], lefts, rights);
  79.         ret.insert(ret.end(), trees.begin(), trees.end());
  80.     }
  81.     return ret;
  82. }
  83. // to print the entire tree
  84. template<typename T>
  85. std::ostream& operator<<(std::ostream& os, Node<T> const& n){
  86.     if (auto with_children = dynamic_cast<NodeWithChildren<T> const*>(&n)){
  87.         os << "(" << with_children->get_left() << " " << n.get() << " " << with_children->get_right() << ")";
  88.     }
  89.     else{
  90.         os << n.get();
  91.     }
  92.     return os;
  93. }
  94. template<typename T>
  95. std::ostream& operator<<(std::ostream& os, std::shared_ptr<T> const& p){
  96.     return os << *p.get();
  97. }
  98. template<typename T>
  99. std::ostream& operator<<(std::ostream& os, std::vector<T> const& v){
  100.     os << "[";
  101.     if (!v.empty())os << v[0];
  102.     for (auto i = 1u; i < v.size(); ++i){
  103.         os << ", " << v[i];
  104.     }
  105.     return os << " ]";
  106. }
  107. /*
  108. * Okay, enough code for manipulating the tree
  109. */
  110. // need some basic elements to fill the tree, that's our `Item` virtual class
  111. class Item{
  112. public:
  113.     virtual ~Item(){}
  114.     virtual void print(std::ostream&)const = 0;
  115. };
  116. std::ostream& operator<<(std::ostream& os, Item const& i){
  117.     i.print(os);
  118.     return os;
  119. }
  120. class Operator :public Item{
  121. public:
  122.     virtual double apply(double, double)const = 0;
  123. };
  124. class Plus :public Operator{
  125. public:
  126.     void print(std::ostream& os)const{
  127.         os << '+';
  128.     }
  129.     Plus(){}
  130.     double apply(double lhs, double rhs)const{
  131.         return lhs + rhs;
  132.     }
  133. };
  134. class Minus :public Operator{
  135. public:
  136.     void print(std::ostream& os)const{
  137.         os << '-';
  138.     }
  139.     Minus(){}
  140.     double apply(double lhs, double rhs)const{
  141.         return lhs - rhs;
  142.     }
  143. };
  144. class Multiple :public Operator{
  145. public:
  146.     void print(std::ostream& os)const{
  147.         os << '*';
  148.     }
  149.     Multiple(){}
  150.     double apply(double lhs, double rhs)const{
  151.         return lhs * rhs;
  152.     }
  153. };
  154. class Divide :public Operator{
  155. public:
  156.     void print(std::ostream& os)const{
  157.         os << '/';
  158.     }
  159.     Divide(){}
  160.     double apply(double lhs, double rhs)const{
  161.         return lhs / rhs;
  162.     }
  163. };
  164. class Number :public Item{
  165.     double value;
  166. public:
  167.     void print(std::ostream& os)const{
  168.         os << value;
  169.     }
  170.     Number(double v) :value(v){}
  171.     double get()const{
  172.         return value;
  173.     }
  174. };
  175. // do the maths
  176. double calc(std::shared_ptr<Node<std::shared_ptr<Item>>> const& n){
  177.     if (auto with_children = dynamic_cast<NodeWithChildren<std::shared_ptr<Item>> const*>(n.get())){
  178.         auto left = calc(with_children->get_left());
  179.         if (auto op = dynamic_cast<Operator const*>(&*n->get())){
  180.             auto right = calc(with_children->get_right());
  181.             return op->apply(left, right);
  182.         }
  183.         std::stringstream ss;
  184.         ss << "expected operator, got ";
  185.         n->get()->print(ss);
  186.         ss << " instead";
  187.         throw ss.str();
  188.     }
  189.     else{
  190.         auto number = dynamic_cast<Number const*>(&*n->get());
  191.         if (number){
  192.             return number->get();
  193.         }
  194.         std::stringstream ss;
  195.         ss << "expected number, got ";
  196.         n->get()->print(ss);
  197.         ss << " instead";
  198.         throw ss.str();
  199.     }
  200. }
  201. class GetNumber{
  202.     bool _empty;
  203.     double _value;
  204. public:
  205.     GetNumber() :_empty(true){}
  206.     void push(char c){
  207.         if (c >= '0' && c <= '9'){
  208.             if (_empty){
  209.                 _value = c - '0';
  210.                 _empty = false;
  211.             }
  212.             else{
  213.                 _value = c - '0' + _value * 10.;
  214.             }
  215.         }
  216.         else{
  217.             std::stringstream ss;
  218.             ss << "unexpected ";
  219.             ss << int(c);
  220.             throw ss.str();
  221.         }
  222.     }
  223.     bool empty(){ return _empty; }
  224.     std::shared_ptr<Number> pop(){
  225.         if (_empty)throw std::exception();
  226.         _empty = true;
  227.         return std::make_shared<Number>(_value);
  228.     }
  229.     void pop(std::vector<std::shared_ptr<Item>>& stack){
  230.         if (!_empty){
  231.             stack.push_back(std::make_shared<Number>(_value));
  232.             _empty = true;
  233.         }
  234.     }
  235. };
  236. // make sure operators and numbers are in the right place
  237. std::vector<std::shared_ptr<Item>>
  238. first_validation(std::vector<std::shared_ptr<Item>> from){
  239.     if (from.empty())throw std::string("empty");
  240.     for (auto i = 0u; i < from.size(); ++i){
  241.         auto item = from[i].get();
  242.         if(i % 2u){
  243.             if (dynamic_cast<Plus*>(item) || dynamic_cast<Minus*>(item) ||
  244.                 dynamic_cast<Multiple*>(item) || dynamic_cast<Divide*>(item)){
  245.                 if (i + 1u == from.size()){
  246.                     std::stringstream ss;
  247.                     ss << "unexpected ";
  248.                     item->print(ss);
  249.                     throw ss.str();
  250.                 }
  251.             }
  252.             else{
  253.                 std::stringstream ss;
  254.                 ss << "unexpected ";
  255.                 item->print(ss);
  256.                 throw ss.str();
  257.             }
  258.         }
  259.         else{
  260.             if (!dynamic_cast<Number*>(item)){
  261.                 std::stringstream ss;
  262.                 ss << "unexpected ";
  263.                 item->print(ss);
  264.                 throw ss.str();
  265.             }
  266.         }
  267.     }
  268.     return from;
  269. }
  270. // read bytes to get a `vector<shared_ptr<Item>>`
  271. std::vector<std::shared_ptr<Item>> read_line(std::istream& in){
  272.     std::vector<std::shared_ptr<Item>> ret;
  273.     GetNumber get_number;
  274.     for (;;) {
  275.         char c;
  276.         in.read(&c, 1);
  277.         if (c >= '0' && c <= '9'){
  278.             get_number.push(c);
  279.         }
  280.         else{
  281.             try{
  282.                 switch (c){
  283.                 case'\n':
  284.                     get_number.pop(ret);
  285.                     return ret;
  286.                 case ' ':
  287.                 case '\r':
  288.                 case '\t':
  289.                     get_number.pop(ret);
  290.                     break;
  291.                 case '+':
  292.                     get_number.pop(ret);
  293.                     ret.push_back(std::make_shared<Plus>());
  294.                     break;
  295.                 case '-':
  296.                     get_number.pop(ret);
  297.                     ret.push_back(std::make_shared<Minus>());
  298.                     break;
  299.                 case '*':
  300.                     get_number.pop(ret);
  301.                     ret.push_back(std::make_shared<Multiple>());
  302.                     break;
  303.                 case '/':
  304.                     get_number.pop(ret);
  305.                     ret.push_back(std::make_shared<Divide>());
  306.                     break;
  307.                 default:
  308.                     throw std::exception();
  309.                 }
  310.             }
  311.             catch (std::exception&){
  312.                 std::stringstream ss;
  313.                 ss << "unexpected " << int(c);
  314.                 while (c != '\n')in.read(&c, 1);
  315.                 throw ss.str();
  316.             }
  317.         }
  318.     }
  319. }
  320. // we count a weight for each tree, to make sure we don't get `42-(1-2)` for `42-1-2`
  321. int count(std::shared_ptr<Node<std::shared_ptr<Item>>> tree){
  322.     if (auto ptr = dynamic_cast<NodeWithChildren<std::shared_ptr<Item>>*>(tree.get())){
  323.         return 2 * count(ptr->get_left()) + count(ptr->get_right());
  324.     }
  325.     return 1;
  326. }
  327. // make sure we do multiplication and division first
  328. bool has_plus_or_minus(std::shared_ptr<Node<std::shared_ptr<Item>>> tree){
  329.     auto ptr = tree.get()->get();
  330.     if (dynamic_cast<Plus*>(ptr.get()) || dynamic_cast<Minus*>(ptr.get())){
  331.         return true;
  332.     }
  333.     if (auto children = dynamic_cast<NodeWithChildren<std::shared_ptr<Item>>*>(tree.get())){
  334.         return has_plus_or_minus(children->get_left()) || has_plus_or_minus(children->get_right());
  335.     }
  336.     return false;
  337. }
  338. // make sure we do multiplication and division first
  339. bool validate(std::shared_ptr<Node<std::shared_ptr<Item>>> tree){
  340.     if (auto with_children = dynamic_cast<NodeWithChildren<std::shared_ptr<Item>>*>(tree.get())){
  341.         auto value = tree->get().get();
  342.         if (dynamic_cast<Multiple*>(value) || dynamic_cast<Divide*>(value)){
  343.             return !has_plus_or_minus(with_children->get_left()) && !has_plus_or_minus(with_children->get_right());
  344.         }
  345.         else{
  346.             return validate(with_children->get_left()) && validate(with_children->get_right());
  347.         }
  348.     }
  349.     return true;
  350. }
  351. /*
  352.  *  `42-1-1` means `(42-1)-1` but not `42-(1-1)`,
  353.  *  and `1+2*3` means `1+(2*3)`, not `(1+2)*3`,
  354.  *  so we use `count()` and `validate()` to filter out incorrect result
  355.  */
  356. TreeList<std::shared_ptr<Item>> filter(TreeList<std::shared_ptr<Item>> from){
  357.     int max = -1;
  358.     std::vector<int> list;
  359.     for (auto i = 0u; i < from.size(); ++i){
  360.         if (validate(from[i])){
  361.             auto cnt = count(from[i]);
  362.             list.push_back(cnt);
  363.             if (cnt > max)max = cnt;
  364.         }
  365.         else{
  366.             list.push_back(-1);
  367.         }
  368.     }
  369.     TreeList<std::shared_ptr<Item>> ret;
  370.     for (auto i = 0u; i < from.size(); ++i){
  371.         if (list[i] == max){
  372.             ret.push_back(from[i]);
  373.         }
  374.     }
  375.     return ret;
  376. }
  377. int main(int argc, char* argv[]){
  378.     if (argc == 2){
  379.         if (std::string("-h") == argv[1] || std::string("--help") == argv[1]){
  380.             std::cout << "try `" << argv[0] << " 1+2` or something" << std::endl;
  381.             return 0;
  382.         }
  383.         std::stringstream ss;
  384.         ss << argv[1];
  385.         ss << '\n';
  386.         try{
  387.             auto items = first_validation(read_line(ss));
  388.             for (auto tree : filter(make_possible_trees(items))){
  389.                 std::cout << tree << " :" << calc(tree) << std::endl;
  390.             }
  391.         }
  392.         catch (std::string& ex){
  393.             std::cout << "error: " << ex << std::endl;
  394.         }
  395.         return 0;
  396.     }
  397.     for (;;){
  398.         try{
  399.             auto items = first_validation(read_line(std::cin));
  400.             for (auto tree : filter(make_possible_trees(items))){
  401.                 std::cout << tree << " :" << calc(tree) << std::endl;
  402.             }
  403.         }
  404.         catch (std::string& ex){
  405.             std::cout << "error: " << ex << std::endl;
  406.         }
  407.     }
  408.     return 0;
  409. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement