akela43

Untitled

Mar 2nd, 2018
203
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <utility>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9.  
  10. struct  Node
  11. {
  12.     int kf; // коэффициент
  13.     int exponent; // степень при x
  14.     Node getDiff(); // производная
  15.     std::string printNode();
  16. //     Node(): kf(1), exponent(1)  {}
  17. //   Node(int _kf, int _exponent) : kf(_kf), exponent(_exponent) {}
  18. };
  19.  
  20. Node Node::getDiff()
  21. {
  22.    return {kf * exponent, (exponent > 0) ? exponent - 1 : 0 };
  23. }
  24.  
  25. std::string Node::printNode()
  26. {
  27.    if (kf == 0) return ""; // ноль не выводим
  28.    else if (exponent == 0) return std::to_string(kf); // число без x
  29.  
  30.    std::string strNode;
  31.    switch (kf) {
  32.    case -1:
  33.        strNode = "-";
  34.        break;
  35.    case 1:
  36.        strNode = "";
  37.        break;
  38.    default:
  39.        strNode = std::to_string(kf) + "*";
  40.        break;
  41.     }
  42.  
  43.    switch (exponent) {
  44.         case 0:
  45.  
  46.             break;
  47.         case 1:
  48.                 strNode += "x";
  49.             break;
  50.         default:
  51.                 strNode += "x^" + std::to_string(exponent);
  52.             break;
  53.         }
  54.         return strNode;
  55.  
  56. }
  57.  
  58. bool sort_function (Node n1, Node n2)
  59. {
  60.     return (n1.exponent < n2.exponent);
  61. }
  62. class Expression
  63. {
  64. public:
  65.     std::vector <Node> vExpression;
  66.     std::string inputStr;
  67.     std::vector <std::string> vStringTerm;
  68.  
  69.     Expression (const std::string &str) :inputStr(str) {
  70.  
  71.     }
  72.     // разделяем строку на слагаемые
  73.     void partToStringTerm() ;
  74.     Node  getNode(const std::string &str) ;
  75.     void parseExpression();
  76.     static std::vector <Node> optimize(std::vector <Node>) ;
  77.  
  78. };
  79.  
  80. Node  Expression::getNode(const string &str)
  81. {
  82.     Node node;
  83.     size_t offset = 0;
  84.     std::string s2;
  85.     std::string s3;
  86.     std::string pozitiveStr;
  87.     //std::string str = _str;
  88.     node.kf = 1;
  89.     node.exponent = 0;
  90.     // отрицательное выражение
  91.     if (str[offset] == '-' ) {
  92.         ++offset;
  93.         node.kf = -1;
  94.     }
  95.  
  96.     if (str.find_first_not_of("0123456789", offset) == std::string::npos)
  97.     {
  98.         // это число
  99.         node.kf = std::stoi(str);
  100.     }
  101.     else
  102.     {
  103.  
  104.         size_t b = str.find('^',offset);
  105.         if (b == std::string::npos ) {
  106.             // это x либо -x
  107.             node.exponent = 1;
  108.  
  109.         } else
  110.    // X^N
  111.         {
  112.             s2 = str.substr(offset, b ); // основание степени
  113.             s3 = str.substr(b+1);   // показатель степени
  114.             node.exponent = std::stoi(s3);  // без исключений. типа все ок
  115.  
  116.         }
  117.     }
  118.  
  119.     return node;
  120. }
  121. void Expression::partToStringTerm() {
  122.  
  123.     size_t start = 0;
  124.     auto length= inputStr.length();
  125.     for  (auto i = start; i <= length; ){
  126.         if (i != length ) {
  127.             if (inputStr[i]== '+') {
  128.                 vStringTerm.push_back(inputStr.substr(start, i - start));
  129.                 start = i + 1;
  130.                 i++;
  131.             }
  132.             else {
  133.                 if (inputStr[i] == '-' && start != i) {
  134.                     // вычитание. добавляем преыдущее слагаемое и продолжаем отчет с той же позиции
  135.                     // чтобы следующее слагаемо было отрицательным
  136.                     vStringTerm.push_back(inputStr.substr(start, i - start));
  137.                     start = i;
  138.                     // i не увеличиваем
  139.                 }
  140.             }
  141.             i++;
  142.         } else {
  143.             // конец строки
  144.             vStringTerm.push_back(inputStr.substr(start, i - start));
  145.             i++; // либо break
  146.         }
  147.     }
  148. }
  149. std::vector <Node> Expression::optimize(std::vector <Node> vExpr)
  150. {
  151.     std::vector <Node> vOptExpr;
  152.  
  153.     for (auto  orig : vExpr )  {
  154.         bool b = true;
  155.         for (auto &opt: vOptExpr) {
  156.             if (opt.exponent == orig.exponent) {
  157.                 // если уже есть элемент с таким основанием
  158.                 opt.kf += orig.kf;
  159.                 b = false;
  160.  
  161.             }
  162.  
  163.         }
  164.         if (b) {
  165.             vOptExpr.push_back(orig);
  166.         }
  167.  
  168.     }
  169.     std::sort (vOptExpr.rbegin(), vOptExpr.rend(),  sort_function);
  170.     return vOptExpr;
  171.  
  172. }
  173. void Expression::parseExpression() {
  174.     for (auto vs: vStringTerm ) {
  175.         Node node0 = {1, 0};
  176.         std::string asterisk = "*";
  177.  
  178.         auto start = 0U;
  179.         auto end = vs.find(asterisk);
  180.         std::vector <std::string> vsNode; // тут хранятся перемножаемые, допустим "-x" * "x^2"
  181.         while (end != std::string::npos)
  182.         {
  183.             vsNode.push_back( vs.substr(start, end - start));
  184.             Node node = getNode(vsNode.back());
  185.             node0.kf *= node.kf;
  186.             node0.exponent += node.exponent;
  187.             start = end + asterisk.length();
  188.             end = vs.find(asterisk, start);
  189.         }
  190.         vsNode.push_back( vs.substr(start, end));
  191.         Node node2 = getNode(vsNode.back());
  192.         node0.kf *= node2.kf;
  193.         node0.exponent += node2.exponent;
  194.         vExpression.push_back(node0);
  195. //       std::sort (vExpression.rbegin(), vExpression.rend(),  sort_function);
  196.        std::vector <Node> optV = Expression:: optimize(vExpression);
  197.        vExpression  = optV;
  198.     }
  199. }
  200. std::string derivative(std::string polynomial) {
  201.     polynomial.erase(std::remove(polynomial.begin(), polynomial.end(), ' '),
  202.                 polynomial.end());
  203.     Expression *expr = new Expression(polynomial);
  204.  
  205.     expr->partToStringTerm();
  206.  
  207.     expr->parseExpression();
  208.     bool bFirst = true;
  209.     std::string ret;
  210.      for(auto var : expr->vExpression) {
  211.  
  212.           Node dVar = var.getDiff();
  213.           if (dVar.kf != 0) {
  214.               if ((!bFirst) && (dVar.kf > 0)) {
  215.                   ret +="+";
  216.                   ret +=dVar.printNode();
  217.   //                std::cout <<"+" << dVar.printNode();
  218.                   bFirst = false;
  219.               }
  220.               else {
  221.  
  222.                   ret +=dVar.printNode();
  223.                   bFirst = false;
  224.               }
  225.           }
  226.           else {
  227.               if (bFirst) ret = "0"; // все выражение равно нулю
  228.           }
  229.     }
  230.     delete expr;
  231.  
  232.     return ret;
  233. }
  234.  
  235.  
  236. int main()
  237. {
  238.     std::string source      = "-x+2*x";
  239.     std::getline(std::cin, source);
  240.     std::string ret = derivative(source);
  241.     std::cout << ret;
  242.  
  243.   return 0;
  244.  
  245. }
Advertisement
Add Comment
Please, Sign In to add comment