fork download
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int str_to_int(char *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. void int_to_str(int val, char *s){ //Записывает в строку s число val.
  26. char tmp[5];
  27. if(val > 0) s[0] = '+'; //Проверка на отрицательность.
  28. else{
  29. val *= -1;
  30. s[0] = '-';
  31. }
  32. int i = 0;
  33. while(val > 0){
  34. tmp[i] = (val%10 + 48); //В tmp хранится запись числа в обратном порядке.
  35. val /= 10;
  36. i++;
  37. }
  38. tmp[i] = 0;
  39. int j = 1;
  40. for(i = strlen(tmp)-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.
  41. s[j] = tmp[i];
  42. j++;
  43. }
  44. s[j] = 0; //Если строка получилась короче пяти символов, нужно поставить после последнего нулевой символ.
  45. }
  46.  
  47. void erase_the_plus(char *s){ //Удаляет плюс, стоящий в начале строки.
  48. if(s[0] == '+'){
  49. for(int i = 0; s[i] != 0; ++i){
  50. s[i] = s[i+1];
  51. }
  52. }
  53. }
  54.  
  55. void erase_the_one(char *s){ //Удаляет единицу из строк вида "+1x", "-1x^y".
  56. if((s[1] == '1') && (strlen(s) == 2)){
  57. s[1] = 0;
  58. }
  59. }
  60.  
  61. void analyze(char *s, vector <int> &v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.
  62. if(strchr(s, 'x') == NULL) v[0] += str_to_int(s, 0, strlen(s)); //Если в строке содержится запись константаы.
  63. else{
  64. if(strchr(s, '^') == NULL) v[1] += str_to_int(s, 0, strchr(s, 'x') - s);//Строка вида "ax".
  65. else{
  66. int power = str_to_int(s, strchr(s, '^') - s + 1, strlen(s));
  67. v[power] += str_to_int(s, 0, strchr(s, 'x') - s);
  68. }
  69. }
  70. }
  71.  
  72. vector <int> decompose(char *s){//Разбивает многочлен на слогаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
  73. vector <int> v(11);
  74. char cur_s[10];
  75. int i = 0, j;
  76. while(s[i] != 0){
  77. //cur_s[0] = 0;
  78. cur_s[0] = s[i];
  79. i++;
  80. j = 1;
  81. while((s[i] != '+') && (s[i] != '-') && (s[i] != 0)){ //cur_s - анализируемое в данный момент слогаемое.
  82. cur_s[j] = s[i];
  83. i++;
  84. j++;
  85. }
  86. cur_s[j] = 0;
  87. analyze(cur_s, v);
  88. }
  89. return v;
  90. }
  91.  
  92. vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.
  93. vector <int> c(21); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
  94. for(int i = 0; i < c.size(); ++i) c[i] = 0;
  95. for(int i = 0; i < a.size(); ++i){
  96. for(int j = 0; j < b.size(); ++j){
  97. c[i + j] += a[i] * b[j];
  98. }
  99. }
  100. return c;
  101. }
  102.  
  103. void compose(char *s, vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен.
  104. for(int i = v.size() - 1; i >= 2; --i){
  105. if(v[i] != 0){
  106. char coef[6]; //Коэффициент.
  107. int_to_str(v[i], coef);
  108. erase_the_one(coef);
  109. strcat(s, coef);
  110. strcat(s, "x");
  111. strcat(s, "^");
  112. char power[2]; //Степень х.
  113. int_to_str(i, power);
  114. erase_the_plus(power);
  115. strcat(s, power);
  116. }
  117. }
  118. if(v[1] != 0){ //Записи слогаемых с первой и нулевой степенями х отличаются.
  119. char coef[10];
  120. int_to_str(v[1], coef);
  121. erase_the_one(coef);
  122. strcat(s, coef);
  123. strcat(s, "x");
  124. }
  125. if(v[0] != 0){
  126. char coef[10];
  127. int_to_str(v[0], coef);
  128. strcat(s, coef);
  129. }
  130. }
  131.  
  132. int main() {
  133. char *a, *b;
  134. int max_number_of_symbols = 100;
  135. a = new char[max_number_of_symbols];
  136. b = new char[max_number_of_symbols];
  137. vector <int> a_decomposed(11, 0);
  138. vector <int> b_decomposed(11, 0);
  139.  
  140. cin.getline(a, max_number_of_symbols); //Ввод многочленов.
  141. cin.getline(b, max_number_of_symbols);
  142. a_decomposed = decompose(a);
  143. b_decomposed = decompose(b);
  144.  
  145. vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);
  146. char *c;
  147. c = new char[max_number_of_symbols];
  148. compose(c, c_decomposed);
  149. erase_the_plus(c); //Удаляется первый плюс, если он есть.
  150. if(strlen(c) > 0) cout << c;
  151. else cout << 0; //Если в ответе получаем константу 0.
  152. return 0;
  153. }
Success #stdin #stdout 0s 15240KB
stdin
x^10
x^10
stdout
x^20