第四道月模csp201809-3 元素选择器

题目背景

题目描述

输入输出

Input

Output

Sample Input

Sample Output

数据规模和约定

思路分析

根据题意，创建element结构体，新建element类型数组e[]，用来存储结构化文档中的元素。
从主函数入手，实现输入输出。
输入有两部分：结构化文档和选择器。
读入结构化文档时由于有属性会出现空格，所以使用getline函数直接读入一整行的数据，读入后再用split函数进行分割。
split函数切分：首先用一个for循环遍历整个字符串，找到第一个非’ .'元素的位置s1和属性出现的开头位置s2。将flag置为2，表示有属性。然后用substr()函数生成子字符串。
为每一个选择器进行选择：
首先用toLower函数将输入的结构化文档全部转化为小写，便于后面比较。非后代选择器的查找，只要遍历一遍数组，判断其属性是否符合条件，符合则将其行号插入vector中；对于后代选择器，调用match函数，从被选择元素开始往前，与vector中元素一一对照，直到两边有一边元素对照完毕，如果是vector中元素对照完毕则说明满足条件，否则不满足。将满足条件的行号插入vector中。
最后，ans中存储的是每个选择器对应的元素，直接输出大小和元素即可。

注意

1.每次处理完一个选择器之后要清空容器
2.标签小写化

AC代码

#include<bits/stdc++.h>
using namespace std;

int n=0,m=0;
struct element{
	string label;   //标签
	string id;      //属性 
	int level;      //目前元素的层级
}e[110];
vector<string> q;  //查询
vector<int> ans;   

void toLower(string &t)
{  //转为小写字母 
	for(int i=0;i<t.size();i++){
		if(t[i]>'A'-1&&t[i]<'Z'+1){
			t[i]=tolower(t[i]);
		}
	}
} 

void split(string &t,int x){
	int suo=0,flag=0;
	int s1=0,s2=0;
	for(int i=0;i<t.size();i++){
		if(t[i]=='.'){suo++;	}
		if(t[i]!='.'&&flag==0){   //记录遇到的第一个非'.'位置 
			flag=1;	 
			s1=i;
		}
		if(t[i]==' '&&flag==1){   //若有属性，记录属性出现位置
			s2=i+1;	
			flag=2;	
			break; 
		}
	}
	string tmp,tmp_id;
	if(flag!=2){   
	//没有属性，只有标签和缩进 
		tmp=t.substr(s1);
		toLower(tmp);   //改为小写
		e[x].label=tmp;
		e[x].level=suo/2; 
	}
	else{   //有属性 
		tmp=t.substr(s1,s2-s1-1);
		toLower(tmp);   //改为小写
		tmp_id=t.substr(s2);
		e[x].label=tmp;
		e[x].id=tmp_id;
		e[x].level=suo/2; 
	}
} 

bool match(int x)、
{  //判断元素是否与选择器匹配 
	int t=e[x].level,qq=q.size()-2;
	for(int i=x-1;i>=0;i--){
		if(e[i].level==t-1){
			if(q[qq][0]!='#'&&q[qq]==e[i].label){qq--;}
            else if(q[qq][0]=='#'&&q[qq]==e[i].id){qq--;}
            t=e[i].level;
            if(qq<0)return true;
		}
	}
	return false;
}

int main(){
	cin>>n>>m;
	string tmp;
	getchar();   
	for(int i=0;i<n;i++)
	{   //读入结构化文档 
		getline(cin,tmp);
		split(tmp,i);
	} 
	
	for(int i=0;i<m;i++)
	{   //读入选择器 
		getline(cin,tmp);
		stringstream st;
		st<<tmp;
		string tt;
		while(st>>tt){
			if(tt[0]!='#'){toLower(tt);	}   //不是id选择器，大小写不敏感 
			q.push_back(tt);
		}
		int qs=q.size();
		for(int j=0;j<n;j++){
			if(q[qs-1][0]=='#'&&q[qs-1]==e[j].id
			||q[qs-1][0]!='#'&&q[qs-1]==e[j].label){
				if(q.size()==1||match(j)){
					ans.push_back(j+1);
				}
			}
		}
		cout<<ans.size();
		for(int i=0;i<ans.size();i++){
			cout<<" "<<ans[i];
		}
		cout<<"\n";
		ans.clear();
		q.clear();
	}
	return 0;
}