Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <utility>
- #include <algorithm>
- using namespace std;
- struct Node
- {
- int kf; // коэффициент
- int exponent; // степень при x
- Node getDiff(); // производная
- std::string printNode();
- // Node(): kf(1), exponent(1) {}
- // Node(int _kf, int _exponent) : kf(_kf), exponent(_exponent) {}
- };
- Node Node::getDiff()
- {
- return {kf * exponent, (exponent > 0) ? exponent - 1 : 0 };
- }
- std::string Node::printNode()
- {
- if (kf == 0) return ""; // ноль не выводим
- else if (exponent == 0) return std::to_string(kf); // число без x
- std::string strNode;
- switch (kf) {
- case -1:
- strNode = "-";
- break;
- case 1:
- strNode = "";
- break;
- default:
- strNode = std::to_string(kf) + "*";
- break;
- }
- switch (exponent) {
- case 0:
- break;
- case 1:
- strNode += "x";
- break;
- default:
- strNode += "x^" + std::to_string(exponent);
- break;
- }
- return strNode;
- }
- bool sort_function (Node n1, Node n2)
- {
- return (n1.exponent < n2.exponent);
- }
- class Expression
- {
- public:
- std::vector <Node> vExpression;
- std::string inputStr;
- std::vector <std::string> vStringTerm;
- Expression (const std::string &str) :inputStr(str) {
- }
- // разделяем строку на слагаемые
- void partToStringTerm() ;
- Node getNode(const std::string &str) ;
- void parseExpression();
- static std::vector <Node> optimize(std::vector <Node>) ;
- };
- Node Expression::getNode(const string &str)
- {
- Node node;
- size_t offset = 0;
- std::string s2;
- std::string s3;
- std::string pozitiveStr;
- //std::string str = _str;
- node.kf = 1;
- node.exponent = 0;
- // отрицательное выражение
- if (str[offset] == '-' ) {
- ++offset;
- node.kf = -1;
- }
- if (str.find_first_not_of("0123456789", offset) == std::string::npos)
- {
- // это число
- node.kf = std::stoi(str);
- }
- else
- {
- size_t b = str.find('^',offset);
- if (b == std::string::npos ) {
- // это x либо -x
- node.exponent = 1;
- } else
- // X^N
- {
- s2 = str.substr(offset, b ); // основание степени
- s3 = str.substr(b+1); // показатель степени
- node.exponent = std::stoi(s3); // без исключений. типа все ок
- }
- }
- return node;
- }
- void Expression::partToStringTerm() {
- size_t start = 0;
- auto length= inputStr.length();
- for (auto i = start; i <= length; ){
- if (i != length ) {
- if (inputStr[i]== '+') {
- vStringTerm.push_back(inputStr.substr(start, i - start));
- start = i + 1;
- i++;
- }
- else {
- if (inputStr[i] == '-' && start != i) {
- // вычитание. добавляем преыдущее слагаемое и продолжаем отчет с той же позиции
- // чтобы следующее слагаемо было отрицательным
- vStringTerm.push_back(inputStr.substr(start, i - start));
- start = i;
- // i не увеличиваем
- }
- }
- i++;
- } else {
- // конец строки
- vStringTerm.push_back(inputStr.substr(start, i - start));
- i++; // либо break
- }
- }
- }
- std::vector <Node> Expression::optimize(std::vector <Node> vExpr)
- {
- std::vector <Node> vOptExpr;
- for (auto orig : vExpr ) {
- bool b = true;
- for (auto &opt: vOptExpr) {
- if (opt.exponent == orig.exponent) {
- // если уже есть элемент с таким основанием
- opt.kf += orig.kf;
- b = false;
- }
- }
- if (b) {
- vOptExpr.push_back(orig);
- }
- }
- std::sort (vOptExpr.rbegin(), vOptExpr.rend(), sort_function);
- return vOptExpr;
- }
- void Expression::parseExpression() {
- for (auto vs: vStringTerm ) {
- Node node0 = {1, 0};
- std::string asterisk = "*";
- auto start = 0U;
- auto end = vs.find(asterisk);
- std::vector <std::string> vsNode; // тут хранятся перемножаемые, допустим "-x" * "x^2"
- while (end != std::string::npos)
- {
- vsNode.push_back( vs.substr(start, end - start));
- Node node = getNode(vsNode.back());
- node0.kf *= node.kf;
- node0.exponent += node.exponent;
- start = end + asterisk.length();
- end = vs.find(asterisk, start);
- }
- vsNode.push_back( vs.substr(start, end));
- Node node2 = getNode(vsNode.back());
- node0.kf *= node2.kf;
- node0.exponent += node2.exponent;
- vExpression.push_back(node0);
- // std::sort (vExpression.rbegin(), vExpression.rend(), sort_function);
- std::vector <Node> optV = Expression:: optimize(vExpression);
- vExpression = optV;
- }
- }
- std::string derivative(std::string polynomial) {
- polynomial.erase(std::remove(polynomial.begin(), polynomial.end(), ' '),
- polynomial.end());
- Expression *expr = new Expression(polynomial);
- expr->partToStringTerm();
- expr->parseExpression();
- bool bFirst = true;
- std::string ret;
- for(auto var : expr->vExpression) {
- Node dVar = var.getDiff();
- if (dVar.kf != 0) {
- if ((!bFirst) && (dVar.kf > 0)) {
- ret +="+";
- ret +=dVar.printNode();
- // std::cout <<"+" << dVar.printNode();
- bFirst = false;
- }
- else {
- ret +=dVar.printNode();
- bFirst = false;
- }
- }
- else {
- if (bFirst) ret = "0"; // все выражение равно нулю
- }
- }
- delete expr;
- return ret;
- }
- int main()
- {
- std::string source = "-x+2*x";
- std::getline(std::cin, source);
- std::string ret = derivative(source);
- std::cout << ret;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment