CCF-CSP認証201912-3.かがくほうていしき

テーマリンク:201912-3化学方程式
難点:
()の多重ネスト複数のネストが発生する可能性があります.一般的な方法は再帰またはスタックで、ここでは「pass」タグを使用して、作業量を軽減します.括弧付きの化学式が出現する形式は(()num 1)num 2)num 3…であるため、下付き順に読み込まれた文字列が出会った最初の数字num 1はnum 1が存在する化学式()num 1を処理する.次にnum 2が存在する化学式()num 2を後処理し、順次処理する.だから、数字に出会った後、前の位置が正しいかどうかによって、一番近い(.
コード1

#include
#include
#include
#include
#include

using namespace std;

map<string, int> mp[2];
typedef pair<string, int> Elem; //     ，string   id ， num     

//   :             ，           
int toNumber(string str, int &pos) {
	int flag = 0;
	while (isdigit(str[pos])) 
		flag = flag * 10 + str[pos++] - '0';
	return flag;
}

void solve(string str, int tag) {
	int coe = 1, pos = 0;		// coe:   ， pos:      
	vector<Elem> arr;			//       
	if (isdigit(str[pos])) coe = toNumber(str, pos); //      ，         

	while (pos < str.size()) {
		if (isdigit(str[pos])) {	//     ，     ，      ，            
			int num = toNumber(str, pos);
			int i = arr.size() - 1;
			if (arr[i].first == ")") {	//       ')'，       '(' , ')'            
				arr[i].first = "pass";	//      ，      ，           
				while (arr[--i].first != "(") arr[i].second *= num; //      '('     
				arr[i].first = "pass";
			}
			else arr[i].second *= num; //         ，      ，         
		}
		else if (str[pos] == '(') { //     
			arr.push_back(Elem("(", 0));
			pos++;
		}
		else if (str[pos] == ')') {
			arr.push_back(Elem(")", 0));
			if (!isdigit(str[++pos])) str.insert(pos, "1"); //   ')'      ，         ‘1’，      ')'    
		}
		else if (isupper(str[pos])) { //     
			string name = "";
			name += str[pos];
			pos++;
			if (islower(str[pos])) { //       
				name += str[pos];
				pos++;
			}
			arr.push_back(Elem(name, 1)); //        1
		}
	}

	for (int i = 0; i != arr.size(); i++) { 
		if (arr[i].first == "pass" ) continue; //        pass
		mp[tag][arr[i].first] += arr[i].second * coe;
	}
}

bool Judge(string str) {
	mp[0].clear();
	mp[1].clear();
	int pos = str.find('=');
	string tmp;
	string left = str.substr(0, pos);
	string right = str.substr(pos + 1);
	stringstream left_ss(left), right_ss(right);

	while (getline(left_ss, tmp, '+')) solve(tmp, 0);
	while (getline(right_ss, tmp, '+')) solve(tmp, 1);

	if (mp[0].size() != mp[1].size()) return false;

	for (map<string, int>::iterator it = mp[0].begin(); it != mp[0].end(); it++) 
		if (mp[1][it->first] != it->second) return false;

	return true;
}

int main() {
	int n;
	string str;
	cin >> n;
	while (n--) {
		cin >> str;
		if (Judge(str)) cout << "Y" << endl;
		else cout << "N" << endl;
	}
	return 0;
}

参照:コード1
コード2
アイデア:unorderedを利用するmap ansは化学方程式全体に現れる原子とその対応する個数を記憶する.
まず=を押して方程式全体を2つの部分に分けます.左のすべての原子の既定の基本係数は1で、右のすべての原子の既定の基本係数は-1です.各部分の最終的な原子の個数にこの基本係数を乗じて、このように完全な方程式の中のすべての原子を処理して、もし引き分けに成功したらすべての原子の対応する個数はすべて0であるべきです;そうでない場合、原子数は0ではありません.
=によって分割された2つの部分について、+によって複数の化学式に分割される.各原子の出現個数を化学式ごとに統計する.
どのように処理しますか?ここで再帰処理の方法は、遭遇するそれぞれ(その対応する位置を探し出し、その()を再帰処理する化学式に対して、そのときの()内の係数にその()の直後の数字を乗じることに注意する.(対応する)を見つける方法は、numを1に初期化し、(その後のすべての文字を遍歴(numに1を加える、1つに出会う)numを1に減らすことであり、num=0の)文字を(対応する)とする.この方法はコード1の方法とも異なり、スタックよりも使いやすい.

else if (formula[i] == '(') {  //  (
            for (int num = 1; num != 0; ++j) {  //     )     j 
                if (formula[j] == '(')
                    ++num;
                else if (formula[j] == ')')
                    --num;
            }
            int k = j;
            f(i + 1, k - 1, e * computeDigit(j, last));  //    
        }

参考:コード2
まとめ:大型シミュレーション問題、細心の注意を払う.