fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6. using namespace std;
  7.  
  8. bool isDigit(char c) { return  c >= '0' && c <= '9';}
  9.  
  10. bool isUpperCaseLetter(char c) { return  c >= 'A' && c <= 'Z'; }
  11.  
  12. bool isLowerCaseLetter(char c) { return  c >= 'a' && c <= 'z'; }
  13.  
  14. void update(map<string, int> &map, string key, int value)
  15. {
  16. 	if (map.count(key))
  17. 	{
  18. 		map.at(key) = map.at(key) + value;
  19. 	}
  20. 	else
  21. 	{
  22. 		map.insert(make_pair(key, value));
  23. 	}
  24. }
  25.  
  26. void split(string formula, vector<string> &storage)
  27. {
  28. 	int begin = 0, length = 0;
  29. 	for (int i = 0; i < formula.length(); i++)
  30. 	{
  31. 		if (formula.at(i) == '+')
  32. 		{
  33. 			storage.push_back(formula.substr(begin, length));
  34. 			length = 1;
  35. 			begin = ++i;
  36. 		}
  37. 		else
  38. 		{
  39. 			length++;
  40. 		}
  41. 	}
  42. 	storage.push_back(formula.substr(begin, length));
  43. }
  44.  
  45. int getMultiplier(string formula)
  46. {
  47. 	int res = 0;
  48. 	for (int i = 0; i < formula.length(); i++)
  49. 	{
  50. 		if (isDigit(formula.at(i)))
  51. 		{
  52. 			res *= 10;
  53. 			res += (formula.at(i) - '0');
  54. 		}
  55. 		else break;
  56. 	}
  57. 	return res == 0 ? 1 : res;
  58. }
  59.  
  60. void getContent(string formula, int multiplier, map<string, int> &content)
  61. { 
  62. 	if (formula.find('(') != string::npos)
  63.     {
  64.         int begin = formula.find('(') + 1;
  65.         int end;
  66.         int bracketCounter = 1;
  67.         for (int i = begin; true; i++)
  68.         {
  69.             if (formula.at(i) == '(')
  70.             {
  71.               	bracketCounter ++;
  72.             }
  73.             else if (formula.at(i) == ')')
  74.             {
  75.                 bracketCounter--;
  76.                 if (bracketCounter == 0)
  77.                 {
  78.                     end = i;
  79.                     break;
  80.                 }
  81.             }
  82.         }
  83.         int newMultiplier = multiplier;
  84.         int afterEnd = end + 1;
  85.         int backCoefficient = 0;
  86.         for (int i = 1; true; i++)
  87.         {
  88.             if (end + i != formula.length() && isDigit(formula.at(end + i)))
  89. 			{
  90. 				backCoefficient *= 10;
  91. 				backCoefficient += (formula.at(end + i) - '0');
  92. 				afterEnd++;
  93. 			}
  94.             else
  95.             {
  96.             	if (backCoefficient == 0)
  97.             	{
  98.             		backCoefficient++;
  99.             	}
  100.             	newMultiplier *= backCoefficient;
  101.                 break;
  102.             }
  103.         }
  104.         if (begin != 1)
  105.         {
  106.         	getContent(formula.substr(0, begin - 1), multiplier, content);
  107.         }
  108.         getContent(formula.substr(begin, end - begin), newMultiplier, content);
  109.         if (afterEnd < formula.length())
  110.         {
  111.         	getContent(formula.substr(afterEnd), multiplier, content);
  112.         }
  113.     }
  114.     else
  115.     {
  116.         string name = "";
  117.         string coefficient = "";
  118.         for (char c : formula)
  119.         {
  120.             if (isDigit(c)) 
  121.             {
  122.             	coefficient += c;
  123.             }
  124.             else if (isLowerCaseLetter(c)) 
  125.             {
  126.             	name += c;
  127.             }
  128.             else if (isUpperCaseLetter(c))
  129.             {
  130.                 if (name.empty()) 
  131.                 {
  132.                 	name += c;
  133.                 }
  134.                 else
  135.                 {
  136.                     if (coefficient.empty()) 
  137.                     {
  138.                     	coefficient = "1";
  139.                     }
  140.                     update(content, name, multiplier * stoi(coefficient));
  141.                     name.clear();
  142.                     name += c;
  143.                     coefficient = "";
  144.                 }
  145.             }
  146.         }
  147.         if (!name.empty())
  148.         {
  149.             if (coefficient.empty()) 
  150.             {
  151.               	coefficient = "1";
  152.             }
  153.             update(content, name, multiplier * stoi(coefficient));
  154.         }
  155.     }
  156. }
  157.  
  158. void process(vector<string> subformulas, map<string, int> &content)
  159. {
  160. 	for (string subformula : subformulas)
  161. 	{
  162. 		int multiplier = getMultiplier(subformula);
  163. 		if (multiplier != 1)
  164. 		{
  165. 			getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content);
  166. 		}
  167. 		else
  168. 		{
  169. 			getContent(subformula, multiplier, content);
  170. 		}
  171. 	}
  172. }
  173.  
  174. int main() 
  175. {
  176. 	string mainFormula;
  177. 	vector<string> mainSubformulas;
  178. 	map<string, int> mainContent;
  179. 	cin >> mainFormula;
  180. 	split(mainFormula, mainSubformulas);
  181. 	process(mainSubformulas, mainContent);
  182. 	int n;
  183. 	cin >> n;
  184. 	string formulaToCompare;
  185. 	vector<string> subformulasToCompare;
  186. 	map<string, int> contentToCompare;
  187. 	for (int i = 0; i < n; i++)
  188. 	{
  189. 		subformulasToCompare.clear();
  190. 		contentToCompare.clear();
  191. 		cin >> formulaToCompare;
  192. 		split(formulaToCompare, subformulasToCompare);
  193. 		process(subformulasToCompare, contentToCompare);
  194. 		cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;
  195. 	}
  196. 	return 0;
  197. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
8Zn+Ar4+Ne
3
Ne(Ar2(Zn)4)2
2Ne(Ar2(Zn)4)
Ne+2Zn2(((((Ar)))))2Zn2
stdout
copy 
8Zn+Ar4+Ne==Ne(Ar2(Zn)4)2
8Zn+Ar4+Ne!=2Ne(Ar2(Zn)4)
8Zn+Ar4+Ne==Ne+2Zn2(((((Ar)))))2Zn2
https://ideone.com/xbEsxG
Алгоритм на строках, рекурсия http://w...content-available-to-author-only...p.com/ru/problems/1072
language:
C++14 (gcc 8.3)
created:
8 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!