CCF-201912-3

这道题虽然思路不是很复杂，但代码写起来可以说是相当复杂。我刚看到这道题时，思路和高中时学化学一样，就是检查两边的元素是否种类和数目一致。我使用了map来存储元素和对应数量的键值对，同时为了方便理解，重载了关于map的一些运算符来简化代码，但最后还是很长。基本上各种复杂情况都考虑到了，如系数有很多位，括号多次嵌套且带有系数等，调试起来也是很花时间的，基本上就是对字符串的分割处理。

#include<iostream>
#include<map>
#include<vector>
#include<string>
using namespace std;

/*test:
4
2Na2((PH3)5NO3)2Au+2H2O=2Na2P10H32O7AuN2+1
H2+O2=2H2O
100CaCl2+200AgNO3=100Ca(NO3)2+200AgCl
1=1
res:
Y
N
Y
Y*/

typedef map<string, int> molecule;

molecule operator+(molecule a, molecule b) {
	molecule res(a);	//从a复制
	molecule::iterator iter;
	for (iter = b.begin(); iter != b.end(); iter++) {
		if (res.count(iter->first)) {
			res.find(iter->first)->second += iter->second;
		}
		else {
			res.insert(pair<string, int>(iter->first, iter->second));
		}
	}
	return res;
}

bool operator==(molecule a, molecule b) {
	molecule::iterator iter;
	if (a.size() != b.size())	return false;
	for (iter = b.begin(); iter != b.end(); iter++) {
		if (a.count(iter->first)) {
			if (a.find(iter->first)->second != iter->second)	return false;
		}
		else {
			return false;
		}
	}
	return true;
}

molecule operator*(int x, molecule b) {
	molecule::iterator iter;
	molecule res;
	for (iter = b.begin(); iter != b.end(); iter++) {
		res.insert(pair<string, int>(iter->first, x*iter->second));
	}
	return res;
}

bool littleLetter(char a) {
	return (a >= 'a' && a <= 'z');
}

bool bigLetter(char a) {
	return (a >= 'A' && a <= 'Z');
}

bool isNumber(char a) {
	return (a >= '0' && a <= '9');
}

molecule dealBrackets(string d){	//从括号开始到结尾括号的系数为止
	int mNum = 1;
	int p = d.length()-1;	//从末尾开始读括号的系数信息
	int l = 0;	//这个数字有多少位
	molecule res;
	while (isNumber(d[p])) {
		p--; l++;
	}
	if(l!=0)
		mNum = atoi(d.substr(p+1, l).c_str());	//在最后处理完成后将系数×上
	int q = 1;	//从括号内第一位开始处理
	while (q != p) {
		if (d[q] == '(') {	//处理嵌套括号
			int startPlace = q;
			int l = 0;
			int frontBrackets = 1;	//遇到的前括号的个数
			while (frontBrackets > 0) {
				q++;	l++;
				if (d[q] == '(')	frontBrackets++;
				if (d[q] == ')')	frontBrackets--;

			}
			l++;	//包含反括号
			if (isNumber(d[q + 1])) {	//将括号后的系数加入子串
				while (isNumber(d[++q]))	l++;
			}
			res = res + dealBrackets(d.substr(startPlace, l));
			continue;
		}
		if (bigLetter(d[q])) {	//一个元素开始
			int startPlace = q;
			if (littleLetter(d[q + 1])) {	//双字母元素
				q++;
				int ENum=1;	//该元素的个数
				if (isNumber(d[q + 1])) {	//get元素背后的系数
					q++;
					int l = 1;
					while (isNumber(d[++q]))	l++;
					ENum = atoi(d.substr(startPlace + 2, l).c_str());
				}
				else {
					q++;
				}
				res.insert(pair<string, int>(d.substr(startPlace, 2), ENum));
			}
			else {	//单字母元素
				int ENum = 1;	//该元素的个数
				if (isNumber(d[q + 1])) {	//get元素背后的系数
					q++;
					int l = 1;
					while (isNumber(d[++q]))	l++;
					string sub = d.substr(startPlace + 1, l);
					ENum = atoi(d.substr(startPlace + 1, l).c_str());
				}
				else {
					q++;
				}
				res.insert(pair<string, int>(d.substr(startPlace, 1), ENum));
			}
		}
	}
	return mNum * res;	//处理完成后将分子系数×上
}

molecule generateMolecule(string d) {	//处理一个分子的入口函数
	if (d[d.length() - 1] == '+') {
		d = d.substr(0, d.length() - 1);
	}
	int p = 0;
	int mNum = 1;	//该分子的前系数，默认为1
	if (isNumber(d[0])) {
		while (isNumber(d[p]))	p++;
		mNum = atoi(d.substr(0, p).c_str());
	}
	int q = p;
	molecule res;
	while (q < d.length()) {
		if (d[q] == ')'|| d[q] == '+')	q++;
		if (d[q] == '(') {	//处理嵌套括号
			int startPlace = q;
			int l = 0;
			int frontBrackets = 1;	//遇到的前括号的个数
			while (frontBrackets > 0) {
				q++;	l++;
				if (d[q] == '(')	frontBrackets++;
				if (d[q] == ')')	frontBrackets--;
				
			}
			l++;	//包含反括号
			if (isNumber(d[q + 1])) {	//将括号后的系数加入子串
				while (isNumber(d[++q]))	l++;
			}
			res = res + dealBrackets(d.substr(startPlace, l));
			continue;
		}
		if (bigLetter(d[q])) {	//一个元素开始
			int startPlace = q;
			if (littleLetter(d[q + 1])) {	//双字母元素
				q++;
				int ENum = 1;	//该元素的个数
				if (isNumber(d[q + 1])) {	//get元素背后的系数
					q++;
					int l = 1;
					while (isNumber(d[++q]))	l++;
					ENum = atoi(d.substr(startPlace + 2, l).c_str());
				}
				else {
					q++;
				}
				res.insert(pair<string, int>(d.substr(startPlace, 2), ENum));
			}
			else {	//单字母元素
				int ENum = 1;	//该元素的个数
				if (isNumber(d[q + 1])) {	//get元素背后的系数
					q++;
					int l = 1;
					while (isNumber(d[++q]))	l++;
					ENum = atoi(d.substr(startPlace + 1, l).c_str());
				}
				else
				{
					q++;
				}
				res.insert(pair<string, int>(d.substr(startPlace, 1), ENum));
			}
		}
	}
	return mNum * res;
}

int main() {
	int numberOfEquation;
	cin >> numberOfEquation;
	cin.ignore();
	
	vector<bool> res;
	for (int i = 0; i < numberOfEquation; i++) {
		string full;
		getline(cin, full);
		int p = 0;
		
		molecule left;
		int startPlace = 0;
		int l = 0;
		while (full[p] != '=') {	//处理左式
			p++;
			l++;
			if (full[p] == '+' || full[p] == '=') {
				string ob = full.substr(startPlace, l);
				left = left + generateMolecule(full.substr(startPlace, l));
				startPlace = p+1;
				l = -1;
			}	
		}
		molecule right;
		l = 0;
		while (p < full.length()) {	//处理右式
			p++;
			l++;
			if (full[p] == '+' || p > full.length() - 1) {
				string ob = full.substr(startPlace, l);
				if (ob == "")	break;
				right = right + generateMolecule(full.substr(startPlace, l));
				startPlace = p + 1;
				l = -1;
			}
		}
		res.push_back(left == right);
	}
	for (int i = 0; i < res.size(); i++) {
		if(res[i])
			cout << "Y" << endl;
		else
		{
			cout << "N" << endl;
		}
	}
	return 0;
}