北郵oj-first集

題目要求

給定一定數量的文法生成式，求出所有非終結符的first集合。

題目思路

由于答案要求，非終結符按照字母順序輸出，非終結符的first集合也需要按照字母順序輸出。是以采用map中加入set的結構。

輸入資料結構定義

struct test {		
	char left;		//生成式左邊的非終結符
	string right;	//生成式右邊的字母集合
};
vector<test> v;		//用于存放輸入案例
           

輸出資料結構定義

周遊一趟所有資料的代碼

for (int i = 0; i < n; i++) {
				char c = v[i].right[0];
				if ((c >= 'a' && c <= 'z') || c == '#') {		//如果右邊第一個字母為 非終結符 或 #，直接将該非終結符加入左邊的first集中，跳過該次循環
					m[v[i].left].insert(c);
					continue;
				} else {
					int j;
					for (j = 0; j < v[i].right.size(); j++) {
						char r = v[i].right[j];
						if ( r >= 'A' && r <= 'Z') {  //如果是非終結符，如果該非終結符first集合中包含#，将所有first集中非#的終結符加入左邊first集中後繼續循環
//							cout <<  v[i].left << " " << r << " = ";
							for (set<char>::iterator it = m[r].begin(); it != m[r].end(); it++) {
								if ((*it) != '#') {
//									cout << (*it) << " ";
									m[v[i].left].insert((*it));
								}
							}
//							cout << endl;
							if (m[r].find('#') == m[r].end()) {	//如果不包含#說明first集合到此結束，跳出循環
								break;
							}
						} else if (r >= 'a' && r <= 'z') {  //如果存在非終結符，直接跳出循環
							m[v[i].left].insert(r);
							break;
						}
					}
					if (j == v[i].right.size()) {	//如果右側所有非終結符的first集中都包含#說明左側的first集中也包含#，将#加入到左側的first集合中
						m[v[i].left].insert('#');
					}
				}

			}
           

包含set的map輸出

for (map<char, set<char> >::iterator iter = m.begin(); iter != m.end(); iter ++) {
			cout << iter->first << " " ;
			set<char>::iterator it = iter->second.begin();
			if (iter->second.find('#') == iter->second.end()) { //判斷該非終結符的first集中有沒有#，如果有的話按照題目要求放到最後輸出
				for ( ; it != iter->second.end(); it++) {
					if (++it == iter->second.end()) {
						it--;
						cout << (*it) << endl;
					} else {
						it--;
						cout << (*it) << " ";
					}
				}
			} else {
				for (it++ ; it != iter->second.end(); it++) {
					cout << (*it) << " ";
				}
				cout << "#" << endl;
			}
		}
           

AC代碼

#include <bits/stdc++.h>
#include <set>
#include <string>
#include <map>
#include <vector>

using namespace std;

struct test {		//用于存放輸入案例
	char left;
	string right;
};

int main() {
	int n;
	while (cin >> n) {
		vector<test> v;
		for (int i = 0; i < n; i++) {
			test t;
			cin >> t.left >> t.right;
			v.push_back(t);
		}
		map<char, set<char> >  m;
		int circle = 5;
		while (circle--) {
			for (int i = 0; i < n; i++) {
				char c = v[i].right[0];
				if ((c >= 'a' && c <= 'z') || c == '#') {
					m[v[i].left].insert(c);
					continue;
				} else {
					int j;
					for (j = 0; j < v[i].right.size(); j++) {
						char r = v[i].right[j];
						if ( r >= 'A' && r <= 'Z') {
//							cout <<  v[i].left << " " << r << " = ";
							for (set<char>::iterator it = m[r].begin(); it != m[r].end(); it++) {
								if ((*it) != '#') {
//									cout << (*it) << " ";
									m[v[i].left].insert((*it));
								}
							}
//							cout << endl;
							if (m[r].find('#') == m[r].end()) {
								break;
							}
						} else if (r >= 'a' && r <= 'z') {
							m[v[i].left].insert(r);
							break;
						}
					}
					if (j == v[i].right.size()) {
						m[v[i].left].insert('#');
					}
				}

			}
		}
		for (map<char, set<char> >::iterator iter = m.begin(); iter != m.end(); iter ++) {
			cout << iter->first << " " ;
			set<char>::iterator it = iter->second.begin();
			if (iter->second.find('#') == iter->second.end()) {
				for ( ; it != iter->second.end(); it++) {
					if (++it == iter->second.end()) {
						it--;
						cout << (*it) << endl;
					} else {
						it--;
						cout << (*it) << " ";
					}
				}
			} else {
				for (it++ ; it != iter->second.end(); it++) {
					cout << (*it) << " ";
				}
				cout << "#" << endl;
			}
		}
	}
	return 0;
}