fork(8) 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
comments (?)
stdin 
x^10+5x^2
x^3-4x
stdout 
x^13-4x^11+5x^5-20x^3
https://ideone.com/B3gZkc
1075. Умножение многочленов. string
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!