题目
输入描述
输出描述
示例
输入
4
B A
A ab
A c
A #
输出
A a c #
B a c #
题解
#include <bits/stdc++.h>
using namespace std;
struct pro
{
char left;
string right;
};
//输出first集
void print(pair<char,set<char>>p)
{
cout<<p.first<<" ";
int empty=0;
for(auto it=p.second.begin(); it!=p.second.end(); it++)
{
if(it==(--p.second.end())&&!empty)
cout<<*it;
else if(*it!='#')
cout<<*it<<" ";
else
empty=1;
}
if(empty==1)
cout<<"#";
cout<<endl;
}
int main()
{
int n;
while(cin>>n)
{
map<char,set<char>>first;
vector<pro>productions;
for(int i=0; i<n; i++)
{
pro p;
cin>>p.left>>p.right;
productions.push_back(p);
}
int circle=5;
while(circle--)
{
for(pro p:productions)
{
char r=p.right[0];
if(r>='a'&&r<='z')//X->a
{
first[p.left].insert(r);
continue;
}
else if(p.right.size()==1&&r=='#')//X->#
{
first[p.left].insert('#');
continue;
}
else if(r>='A'&&r<='Z')//X->AB
{
int add=0;//添加#
for(char t:p.right)
{
for(char nt:first[t])
{
if(nt!='#')
first[p.left].insert(nt);
else
add++;
}
}
if(add==p.right.size())
first[p.left].insert('#');
}
}
}
for_each(first.begin(), first.end(), print);//打印first集
}
}
相关题目
2011 网研 ProblemA 字符串操作
2011 网研 ProblemB 虚数
2011 网研 ProblemC 中序遍历树
2011 网研 ProblemD first集