CCF CSP 元素选择器

解析

参考blog:元素选择器
大佬的代码真是思路清晰，而且代码风格有很强的编程技巧性，看来还是任重而道远啊！加油！

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <sstream>

using namespace std;

struct node{
	string name,tag;
	int level;
	node* parent;
	node(string n,string t,int l):name(n),tag(t),level(l),parent(0) {}
}; 

void divide(const string& line,vector<string>& sel)
{
	sel.clear();
	string token;
	token.clear();
	for(int i=0;i<line.size();i++)
	{
		if(line[i]==' ')
		{
			sel.push_back(token);
			token.clear();
		}
		else token+=line[i];
	}
	sel.push_back(token);
}

bool check(node* t,const string& s)
{
	if(s[0]=='#') return s==t->tag;
	if(s.size()!=t->name.size()) return false;
	for(int i=0;i<s.size();i++)
	{
		if(tolower(s[i])!=tolower(t->name[i])) return false;
	}
	return true;
}

int main()
{
	//freopen("input/selector.txt","r",stdin);
	int n,m;
	scanf("%d%d",&n,&m);
	
	vector<node*> nodes;
	nodes.clear();
	stack<node*> parents;
	while(!parents.empty()) parents.pop();
	
	string line;
	getline(cin,line);
	while(n--)
	{
		getline(cin,line);
		int level=0;
		while(line[level]=='.') level++;
		stringstream ss(line.substr(level));
		string name,tag;
		ss>>name>>tag;
		node* now=new node(name,tag,level);
		if(!parents.empty())
		{
			node* p;
			while(p=parents.top(),p->level>=level)
			{
				parents.pop();
			}
			now->parent=p;
			//cout<<now->name<<"'s parent is "<<now->parent->name<<endl;
		}
		parents.push(now);
		nodes.push_back(now);
	} 
	
	vector<int> ans;
	vector<string> sel;
	while(m--)
	{
		getline(cin,line);
		divide(line,sel);
		ans.clear();
		for(int i=0;i<nodes.size();i++)
		{
			int sl=sel.size()-1;
			if(check(nodes[i],sel[sl]))
			{
				node* t=nodes[i]->parent;
				sl--;
				while(t&&sl>=0)
				{
					if(check(t,sel[sl])) sl--;
					t=t->parent;
				}
				if(sl==-1) ans.push_back(i+1);
			}
		}
		
		printf("%d ",ans.size());
		for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
		if(m!=0) printf("\n");
	}
	return 0;
}