题目

BUPT 2011 网研 ProblemD（oj）

输入描述

输出描述

示例

输入

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集