csp-化学方程式

化学方程式

这是一个化学方程式检测的算法题，只是检测物料守恒，题目不是特别难，但是字符串处理时还是挺繁琐的，假期一直宅在家里，好久没更新博客了。算是记录一下解题的思路把。

下面是完整代码

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
using namespace std;

struct element {
	string s;
	int amount;
	element() :s(""), amount(0) {};
	element(string st) :s(st), amount(0) {};
	element(string st, int a) :s(st), amount(a) {};
	bool operator < (const element& e) {
		return s < e.s;
	}
	bool operator == (const element& e) {
		return s == e.s;
	}
};


class elements {
public:
	vector<element> es;
	elements() {};
	elements(element e) {
		es.push_back(e);
	}
	void add_element(string ele_name, int amount) {
		element t_e = element(ele_name, amount);
		auto i = find(es.begin(), es.end(), t_e);
		if (i == es.end()) {
			es.push_back(t_e);
		}
		else {
			i->amount += amount;
		}
	}

	void show() {
		for (auto t : es) {
			cout << t.s << '\t' << t.amount << endl;
		}
		cout << endl << endl;
	}

	void up_elements(elements& e_t, int mul_num) {
		for (auto i : e_t.es) {
			auto j = find(es.begin(), es.end(), i);
			if (j == es.end()) {
				i.amount *= mul_num;
				es.push_back(i);
			}
			else {
				j->amount += i.amount * mul_num;
			}
		}
	}

	bool operator == (const elements& es_t) {
		if (es_t.es.size() != es.size()) {
			return false;
		}
		for (int i = 0; i < es.size(); i++) {
			if (es[i].s != es_t.es[i].s || es[i].amount != es_t.es[i].amount) {
				return false;
			}
		}
		return true;
	}

	bool is_equal(elements& es_t) {
		sort(es.begin(), es.end());
		sort(es_t.es.begin(), es_t.es.end());
		if (*this == es_t) {
			return true;
		}
		return false;
	}
};

elements r_left, r_right;
vector<string> l_s, r_s;
char result[100];
stringstream ss;

void split_s(string s) {
	ss.clear();
	ss.str(s);
	string tmp[2];
	int i_t = 0;
	string tmp_s;
	while (getline(ss, tmp[i_t++], '='));
	ss.clear();
	ss.str(tmp[0]);
	while (getline(ss, tmp_s, '+')) {
		l_s.push_back(tmp_s);
	}
	ss.clear();
	ss.str(tmp[1]);
	while (getline(ss, tmp_s, '+')) {
		r_s.push_back(tmp_s);
	}
}

elements cal(string s) {
	elements r_tmp;
	int prefix_num;
	string prefix_str;

	string e_s_t;

	int j_tmp = 0;

	while (s[j_tmp] >= '0' && s[j_tmp] <= '9') {
		prefix_str += s[j_tmp];
		j_tmp++;
	}
	prefix_num = prefix_str.size() ? stoi(prefix_str) : 1;

	while (1) {
		if (j_tmp < s.size()) {
			if (s[j_tmp] >= 'A' && s[j_tmp] <= 'Z') {
				if (e_s_t.size()) {
					r_tmp.add_element(e_s_t, prefix_num);
					e_s_t.clear();
				}
				e_s_t += s[j_tmp];
				j_tmp++;
			}
			else if (s[j_tmp] >= 'a' && s[j_tmp] <= 'z') {
				e_s_t += s[j_tmp];
				j_tmp++;
			}
			else if (s[j_tmp] >= '0' && s[j_tmp] <= '9') {
				string inner_str;
				int inner_num;
				while (j_tmp < s.size() && s[j_tmp] >= '0' && s[j_tmp] <= '9') {
					inner_str += s[j_tmp];
					j_tmp++;
				}
				inner_num = inner_str.size() ? stoi(inner_str) : 1;
				r_tmp.add_element(e_s_t, inner_num * prefix_num);
				e_s_t.clear();
			}
			else if (s[j_tmp] == '(') {
				if (e_s_t.size()) {
					r_tmp.add_element(e_s_t, prefix_num);
					e_s_t.clear();
				}
				int pos1 = j_tmp + 1;
				int flag = 0;
				while (1) {
					if (s[j_tmp] == '(') {
						flag++;
					}
					if (s[j_tmp] == ')') {
						flag--;
					}
					if (flag == 0) {
						j_tmp++;
						break;
					}
					j_tmp++;
				};
				int pos2 = j_tmp - 1;
				int size_tmp = pos2 - pos1;
				string deep_string = s.substr(pos1, size_tmp);
				elements r_tmp_e = cal(deep_string);

				string inner_str;
				int inner_num;
				if (j_tmp < s.size() && s[j_tmp] >= '0' && s[j_tmp] <= '9') {
					while (j_tmp < s.size() && s[j_tmp] >= '0' && s[j_tmp] <= '9') {
						inner_str += s[j_tmp];
						j_tmp++;
					}
				}
				inner_num = inner_str.size() ? stoi(inner_str) : 1;
				r_tmp.up_elements(r_tmp_e, inner_num* prefix_num);
			}
		}
		else {
			if (e_s_t.size()) {
				r_tmp.add_element(e_s_t, prefix_num);
				e_s_t.clear();
			}
			break;
		}
	}
	return r_tmp;
}

void calc() {
	elements e_tmp;
	for (auto& i : l_s) {
		e_tmp = cal(i);
		r_left.up_elements(e_tmp, 1);
	}
	for (auto& i : r_s) {
		e_tmp = cal(i);
		r_right.up_elements(e_tmp, 1);
	}
	l_s.clear();
	r_s.clear();
}


void sol() {
	int n;
	cin >> n;
	string tmp_s;
	for (int i = 0; i < n; i++) {
		cin >> tmp_s;
		split_s(tmp_s);
		calc();
		if (r_left.is_equal(r_right)) {
			result[i] = 'Y';
		}
		else {
			result[i] = 'N';
		}
		//r_left.show();
		//r_right.show();
		r_left.es.clear();
		r_right.es.clear();
	}
	int pos = 0;
	while (result[pos] == 'N' || result[pos] == 'Y') {
		cout << result[pos]<<endl;
		pos++;
	}
}

int main() {
	sol();
	return 0;
}

这里的核心算法其实就是cal函数，这个函数主要是拆分字符串为基本元素符号，并统计个数，比如说将"2H2O拆分成两个struct，e1=element(‘H’,4),e2=element(‘O’,2)",下面分析一下这个函数.

struct element {
	string s;
	int amount;
	element() :s(""), amount(0) {};
	element(string st) :s(st), amount(0) {};
	element(string st, int a) :s(st), amount(a) {};
	bool operator < (const element& e) {
		return s < e.s;
	}
	bool operator == (const element& e) {
		return s == e.s;
	}
};


class elements {
public:
	vector<element> es;
};

elements cal(string s) {
	elements r_tmp;
	int prefix_num;
	string prefix_str;

	string e_s_t;

	int j_tmp = 0;

	while (s[j_tmp] >= '0' && s[j_tmp] <= '9') {
		prefix_str += s[j_tmp];
		j_tmp++;
	}
	prefix_num = prefix_str.size() ? stoi(prefix_str) : 1;

	while (1) {
		if (j_tmp < s.size()) {
			if (s[j_tmp] >= 'A' && s[j_tmp] <= 'Z') {
				if (e_s_t.size()) {
					r_tmp.add_element(e_s_t, prefix_num);
					e_s_t.clear();
				}
				e_s_t += s[j_tmp];
				j_tmp++;
			}
			else if (s[j_tmp] >= 'a' && s[j_tmp] <= 'z') {
				e_s_t += s[j_tmp];
				j_tmp++;
			}
			else if (s[j_tmp] >= '0' && s[j_tmp] <= '9') {
				string inner_str;
				int inner_num;
				while (j_tmp < s.size() && s[j_tmp] >= '0' && s[j_tmp] <= '9') {
					inner_str += s[j_tmp];
					j_tmp++;
				}
				inner_num = inner_str.size() ? stoi(inner_str) : 1;
				r_tmp.add_element(e_s_t, inner_num * prefix_num);
				e_s_t.clear();
			}
			else if (s[j_tmp] == '(') {
				if (e_s_t.size()) {
					r_tmp.add_element(e_s_t, prefix_num);
					e_s_t.clear();
				}
				int pos1 = j_tmp + 1;
				int flag = 0;
				while (1) {
					if (s[j_tmp] == '(') {
						flag++;
					}
					if (s[j_tmp] == ')') {
						flag--;
					}
					if (flag == 0) {
						j_tmp++;
						break;
					}
					j_tmp++;
				};
				int pos2 = j_tmp - 1;
				int size_tmp = pos2 - pos1;
				string deep_string = s.substr(pos1, size_tmp);
				elements r_tmp_e = cal(deep_string);

				string inner_str;
				int inner_num;
				if (j_tmp < s.size() && s[j_tmp] >= '0' && s[j_tmp] <= '9') {
					while (j_tmp < s.size() && s[j_tmp] >= '0' && s[j_tmp] <= '9') {
						inner_str += s[j_tmp];
						j_tmp++;
					}
				}
				inner_num = inner_str.size() ? stoi(inner_str) : 1;
				r_tmp.up_elements(r_tmp_e, inner_num* prefix_num);
			}
		}
		else {
			if (e_s_t.size()) {
				r_tmp.add_element(e_s_t, prefix_num);
				e_s_t.clear();
			}
			break;
		}
	}
	return r_tmp;
}

上面的代码没怎么写注释，习惯了，尽管知道不太好，但是一直没改。
下面说一下字符串分解函数

• 计算前缀数字，也就是化学物质的摩尔数
• 遍历元素，会遇到5种情况
• 1）大写字母，这时如果前面不是数字，则需要存储前面的element，数量为前缀长度，然后遍历下一个
• 2）小写字母，这时遍历下一个字符
• 3）数字，这里有一个注意点，需要注意边界，这是需要进行添加element操作
• 4）括号，这是最麻烦的一部，这里有一个比较坑的地方是需要注意括号嵌套括号的情况，所以使用了下面的一段代码，接着便是递归。

int flag = 0;
				while (1) {
					if (s[j_tmp] == '(') {
						flag++;
					}
					if (s[j_tmp] == ')') {
						flag--;
					}
					if (flag == 0) {
						j_tmp++;
						break;
					}
					j_tmp++;
				};

• 5）字符遍历越界，这里也是需要判断处理的。

这道题还是花了很长时间才做出来的，如果再考场上的话，拿不到满分，能解决还是很happy的。