fork(1) download
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int str_to_int(string &s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).
  7. int val = 0; //Возвращает объект типа int, значение которого равно этому числу.
  8. bool negative = 0; //Является ли число отрицательным?
  9. if(s[begin] == '+') begin++;//Плюс игнорируется.
  10. else{
  11. if(s[begin] == '-'){ //Проверка на отрицательность.
  12. negative = 1;
  13. begin++;
  14. }
  15. }
  16. for(auto i = begin; i < end; ++i){ //Обработка самих цифр числа.
  17. val *= 10;
  18. val += s[i] - 48;
  19. }
  20. if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица
  21. if(negative == 1) val *= -1;
  22. return val;
  23. }
  24.  
  25. string int_to_str(int val){ //Возвращает строку с записанным в ней числом val.
  26. string s, tmp;
  27. if(val > 0) s.push_back('+'); //Проверка на отрицательность.
  28. else{
  29. val *= -1;
  30. s.push_back('-');
  31. }
  32. while(val > 0){
  33. tmp.push_back(val%10 + 48); //В tmp хранится запись числа в обратном порядке.
  34. val /= 10;
  35. }
  36. for(int i = tmp.size()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.
  37. s.push_back(tmp[i]);
  38. }
  39. return s;
  40. }
  41.  
  42. void erase_the_plus(string &s){ //Удаляет плюс, стоящий в начале строки.
  43. if(s[0] == '+') s.erase(s.begin());
  44. }
  45.  
  46. void erase_the_one(string &s){ //Удаляет единицу из строк вида "+1x", "-1x^y".
  47. if((s[1] == '1') && (s.size() == 2)) s.erase(s.begin()+1);
  48. }
  49.  
  50. void analyze(string &s, vector <int> &v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.
  51. if(s.find("x") == string::npos) v[0] += str_to_int(s, 0, s.size()); //Если в строке содержится запись константаы.
  52. else{
  53. if(s.find("^") == string::npos) v[1] += str_to_int(s, 0, s.find("x")); //Строка вида "ax".
  54. else{
  55. int power = str_to_int(s, s.find("^") + 1, s.size()); //Строка вида "ax^y".
  56. v[power] += str_to_int(s, 0, s.find("x"));
  57. }
  58. }
  59. }
  60.  
  61. vector <int> decompose(string &s){ //Разбивает многочлен на слогаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
  62. vector <int> v(11);
  63. string cur_s;
  64. int i = 0;
  65. while(i < s.size()){
  66. cur_s.clear();
  67. cur_s.push_back(s[i]);
  68. i++;
  69. while((s[i] != '+') && (s[i] != '-') && (i < s.size())){ //cur_s - анализируемое в данный момент слогаемое.
  70. cur_s.push_back(s[i]);
  71. i++;
  72. }
  73. analyze(cur_s, v);
  74. }
  75. return v;
  76. }
  77.  
  78. vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.
  79. vector <int> c(21); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
  80. for(int i = 0; i < c.size(); ++i) c[i] = 0;
  81. for(int i = 0; i < a.size(); ++i){
  82. for(int j = 0; j < b.size(); ++j){
  83. c[i + j] += a[i] * b[j];
  84. }
  85. }
  86. return c;
  87. }
  88.  
  89. string compose(vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен.
  90. string s;
  91. for(int i = v.size() - 1; i >= 2; --i){
  92. if(v[i] != 0){
  93. string coef = int_to_str(v[i]); //Коэффициент.
  94. erase_the_one(coef);
  95. s = s + coef;
  96. s.push_back('x');
  97. s.push_back('^');
  98. string power = int_to_str(i); //Степень х.
  99. erase_the_plus(power);
  100. s = s + power;
  101. }
  102. }
  103. if(v[1] != 0){ //Записи слогаемых с первой и нулевой степенями х отличаются.
  104. string coef = int_to_str(v[1]);
  105. erase_the_one(coef);
  106. s = s + coef;
  107. s.push_back('x');
  108. }
  109. if(v[0] != 0){
  110. s = s + int_to_str(v[0]);
  111. }
  112. return s;
  113. }
  114.  
  115. int main() {
  116. string a,b;
  117. vector <int> a_decomposed(11, 0);
  118. vector <int> b_decomposed(11, 0);
  119. getline(cin, a); //Ввод многочленов.
  120. getline(cin, b);
  121. a_decomposed = decompose(a);
  122. b_decomposed = decompose(b);
  123. vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);
  124. string c = compose(c_decomposed);
  125. erase_the_plus(c); //Удаляется первый плюс, если он есть.
  126. if(c.size() > 0) cout << c;
  127. else cout << 0; //Если в ответе получаем константу 0.
  128. return 0;
  129. }
Success #stdin #stdout 0s 16072KB
stdin
x^10+5x^2
x^3-4x
stdout
x^13-4x^11+5x^5-20x^3