元素选择器

问题背景

层叠样式表 (Cascading Style Sheets, 缩写 CSS) 是一种用来为结构化文档 (如 HTML 文档) 添加样式 (字体、间距和颜色等) 的计算机语言。例如，对于以下的 HTML 文档：

<html>
    <head>
        <title>Sample</title>
    </head>
    <body>
        <h1>Hello</h1>
        <p id="Subtitle">Greetings</div>
        <p>Hello, world!</p>
    </body>
</html>

配合以下 CSS 片段可以为其中的标题和段落设置相应的格式：

h1 { font-weight: bold; }
#subtitle { font-size: 12px; }

这段 CSS 片段为前面 HTML 文档添加了样式，使得标题 “Hello” 具有粗体，使得段落 “Greetings” 具有 12 个像素的字体大小。这里，CSS 片段第 1 行中出现的 h1 是一个选择器，它选中了 HTML 文档第 6 行的 h1 元素。CSS片段第 2 行中出现的 #subtitle 也是一个选择器，选中了 HTML 文档第 7 行 id 属性为 subtitle 的 p 元素。注意它并没有选中 HTML 文档第 8 行不带属性的 p 元素。

问题描述

本题要求实现一个简化版的元素选择器。给出一个结构化文档，和若干个选择器，对每个选择器找出文档中所对应选中的元素。

【结构化文档】结构化文档由元素组成，一个元素可以包含若干个子元素 (可以没有)。一个文档有一个跟元素，在整体上形成树的结构。以下是本题结构化文档的一个例子：

html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #one
......div
........p #two

文档中每行表示一个元素，元素的标签由一个或者多个字母或数字组成。标签大小写不敏感，例如 div、Div、DIV 都是同一类标签。
元素可以附加一个 id 属性，属性值也是由一个或者多个字母或数字组成，之前有一个井号 #。id 属性大小写敏感，例如 a 和 A 是两个不同的 id。如果元素有 id 属性，标签和属性之间用一个空格字符分隔。
标签之前的缩进表示元素之间的包含关系：一个元素 E 所在行之后连续的缩进更深的行代表的元素是元素 E 的后代元素，其中缩进恰好深一层的是元素 E 的子元素。为了便于观察，每一级缩进用两个小数点符号 .. 表示。

【选择器】  本题中出现的选择器有三种，分别为：
[标签选择器] 用标签来表示。例如 p 表示选择标签为 p 的所有元素。
[id 选择器] 用 id 属性来表示。例如 #main 表示选择 id 属性为 main 的元素。题目保证文档中不同的元素不会有相同的 id 属性。
[后代选择器] 复合表达式，格式为 A B ，其中 A 和 B 均为 标签选择器或 id 选择器，中间用一个空格字符分隔，表示选择满足选择器 B 的所有元素，且满足这些元素有祖先元素满足选择器 A 。例如，选择器 div p 在上面的文档中会选中最后一行的元素 p ，但不会选中 id 属性为 subtitle 的那个元素 p 。注意，后代选择器可以有更多的组成部分构成， div p 是一个两级的后代选择器，而 div div p 则是一个三级的后代选择器。

Input

输入第一行是两个正整数 n, m (1 ≤ n ≤ 100, 1 ≤ m ≤ 10)，分别表示结构化文档的行数，和待查询的选择器的个数，中间用一个空格字符分隔。
第 2 行至 第 n + 1 行逐行给出结构化文档的内容。
第 n + 2 行至第 n + m + 1 行每行给出一个待查询的选择器。记第 n + 1 + i 行的选择器为 si， 1 ≤ i ≤ m。
结构化文档和待查询的选择器每行长度不超过 80 个字符(不包括换行符)，保证输入的结构化文档和待查询的选择器都是合法的。

Output

输出共 m 行，每行有若干个整数。第 i 行表示选择器 si 选中的结果 (1 ≤ i ≤ m)。其中第一个整数 ri 表示 si 选中的元素个数。随后 ri 个整数，分别表示选中元素在结构化文档中出现的行号(行号从 1 开始编号)。行号按从小到大排序，相邻整数之间用一个空格字符分隔。

Sample

Input: 
11 5
html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #one
......div
........p #two
p
#subtitle
h3
div p
div div p

Output: 
3 6 9 11
1 6
0
2 9 11
1 11

Explain:
对于样例中查询的 5 个选择器：
1. p 选中所有的元素 p ；
2. #subtitle 选中第 6 行 id 属性为 subtitle 的元素 p ；
3. 由于没有标签为 h3 的元素，因此 h3 没有选中任何元素；
4. 第 9 行和第 11 行的 p 元素都有祖先是 div 元素，而第 6 行的 p 元素 没有祖先是 div 元素；
5. div div p 要求选中的 p 元素有两级祖先都是 div 元素，只有第 11 行的 p 元素满足这个条件。

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

~~题目太长了，输入格式还不够 HTML 直观。~~

..的数量可以看成级数，整体可以看成文件目录，若没有 .. 则为根目录，每一次 .. 的增加都是在当前目录下开出了一个新目录，样例可以变成：

很明显的具有树形结构。根据题意，输入一定是按 HTML 文档顺序输入的，要求也只是查找，因此可以用数组或向量存储数据，不用建立树的结构。

储存的时候，处理数据，根据 .. 赋值级数，根据是否有 # 处理 id、标签，并且标签全部转化为小写。并同时用一个变量 father 从后往前遍历向量，标记父节点位置，方便多级查询。

查询的时候，分隔 string，判断是哪一种选择器；若 substring 个数为1，则只需顺序遍历向量进行查询，根据 # 判断是否需要大小写处理；若不只有一个 substring，则从后往前遍历向量，从后往前逐级“剥去” id 或标签，找到就 push 行数。

最后根据题意输出。

源代码

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

struct node {
	int lev, fa;
	string label, id;
	node() { lev = -2; fa = -2; }
	node(int l, int f, string la, string ID) :lev(l), fa(f), label(la), id(ID) {  }
};

vector<node> v;

char lowerCase(char c) {
	if (c >= 65 && c <= 90)
		c += 32;
	return c;
}

void initial(string s) {
	int pos = 0;
	while (s[pos] == '.')
		pos++;
	int lev = pos / 2;
	int fa;
	if (v.empty() || lev == 0)
		fa = -1;
	else {
		for (int i = v.size() - 1; i >= 0; i--) {
			if (v[i].lev == lev - 1) {
				fa = i;
				break;
			}
		}
	}
	string la, ID;
	bool labeled = false;
	while (pos < s.size()) {
		if (s[pos] == '#' || labeled) {
			labeled = true;
			la += s[pos];
		}
		else {
			if (s[pos] != ' ')
				ID += lowerCase(s[pos]);
		}
		pos++;
	}
	node tnode(lev, fa, la, ID);
	v.push_back(tnode);
}

string lowerCaseString(string s) {
	for (int i = 0; i != s.size(); i++)
		s[i] = lowerCase(s[i]);
	return s;
}

vector<int> lookup(string s) {
	vector<int> ans;
	int pos = 0;
	stringstream ss(s);
	vector<string> sv;
	while (!ss.eof()) {
		string stemp;
		ss >> stemp;
		if (stemp[0] != '#')
			stemp = lowerCaseString(stemp);
		sv.push_back(stemp);
	}
	for (int i = v.size() - 1; i >= 0; i--) {
		int pos2 = sv.size() - 1;
		if (sv[pos2] != v[i].label && sv[pos2] != v[i].id)
			continue;
		pos = v[i].fa;
		pos2--;
		while (pos >= 0 && pos2 >= 0) {
			if (v[pos].label == sv[pos2] || v[pos].id == sv[pos2])
				pos2--;
			pos = v[pos].fa;
		}
		if (pos2 == -1)
			ans.push_back(i + 1);
	}
	reverse(ans.begin(), ans.end());
	return ans;
}

int main() {
	int n, m;
	cin >> n >> m;
	cin.ignore();
	v.clear();
	while (n--) {
		string s;
		getline(cin, s);
		initial(s);
	}
	while (m--) {
		string s;
		getline(cin, s);
		vector<int> ans = lookup(s);
		if (ans.empty())
			cout << "0" << endl;
		else {
			cout << ans.size();
			for (int i = 0; i != ans.size(); i++)
				cout << " " << ans[i];
			cout << endl;
		}
	}

	return 0;
}

荒芜知地

201809-3-元素选择器