北邮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;
}