week15——实验（月模拟题4：CSP201809 03）

元素选择器 ：

问题描述

题目简述

问题分析

解题思路

本题要求实现3个不同类型的html元素选择器。实际上，通过分析可以发现，这三种选择器可以统一成一种情况，因为如果将“#”看成匹配的一部分的话，标签选择器和id选择器是一样的，而后代选择器，相当于一次选取多个有包含顺序的标签，因此，其本质上是一个标签选择器。因此，这三种选择器用一种方法即可实现。我的思路是先从最低级的元素开始匹配，当匹配到该元素时，如果是标签和id选择器，该搜索过程已经结束，但对于后代选择器，需要继续匹配外层的标签，而其父代一定位于当前匹配的元素之前，因此，需要通过循环继续匹配，从当前位置开始，每次匹配若成功匹配一层，那么就将起始位置改为该位置，并匹配下一层，直到匹配完全为止。其他两个选择器不需要进行此循环。
以上是匹配部分，之后就是字符串的处理，首先对于输入的html代码，需要去掉内容前的“."并统计数量，之后找到标签和属性的起始位置。将以上信息保存到一个结构体中即可。对于输入的查询，需要将各部分分隔开的空格去掉，使用stringstream即可完美解决。
之后问题就解决了。

参考代码

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

class elements
{
public:
	string label;
	string id;
	int count;
};

void string_lower(string& s)
{
	for(int i=0;i<s.length();i++)
	{
		s[i]=tolower(s[i]);
	}
}

bool search(elements e[],int& start,int& count,string s)
{
	for(int i=start;i>=1;i--)
	{
		if(e[i].count<count)
		{
			start=i;
			count=e[i].count;
			if(e[i].label==s||e[i].id==s) return true;
		}
	}
	return false;
}

int main()
{
	elements element[105];
	int n,m;
	cin>>n>>m;
	getchar();
	for(int i=1;i<=n;i++)
	{
		string ss;
		getline(cin,ss);
		//cout<<ss<<endl;
		int pos1=-1;
		int pos2=-1;
		int cc=0;
		for(int j=0;j<ss.length();j++)
		{
			if(ss[j]=='.') cc++;
			else if(pos1==-1&&ss[j]!='#') pos1=j;
			else if(ss[j]=='#') pos2=j;
		}
		element[i].count=cc;
		if(pos2==-1)
		{
			element[i].label=ss.substr(pos1);
			element[i].id="";
		}
		else 
		{
			element[i].label=ss.substr(pos1,pos2-pos1-1);
			element[i].id=ss.substr(pos2);
		}
		string_lower(element[i].label);
	}
	for(int i=1;i<=m;i++)
	{
		string ss;
		getline(cin,ss);
		vector<string> v;
		vector<int> ans;
		stringstream in(ss);
		string temp;
		while(in>>temp)
		{
			v.push_back(temp);
		} 
		int len=v.size();
		for(int i=0;i<len;i++)
		{
			if(v[i][0]!='#') string_lower(v[i]);
		}
		for(int j=1;j<=n;j++)
		{
			//cout<<"element"<<j<<"message: id:"<<element[j].id<<" label:"<<element[j].label<<" count:"<<element[j].count<<endl;
			if(v[len-1]==element[j].id||v[len-1]==element[j].label)
			{
				int k=len-2;
				int start=j;
				int count=element[j].count;
				for(k;k>=0;k--)
				{
					if(!search(element,start,count,v[k])) break;
				}
				if(k<0) ans.push_back(j);
			}
		}
		cout<<ans.size()<<" ";
		for(int t=0;t<ans.size();t++)
		{
			cout<<ans[t]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

心得体会

这个题我想了很久才想出来这个方法，最后AC了也是非常的高兴。模拟题还是要多练，感觉做题的时候思路还不算很清晰，还是要继续练习。