题目主干

题目描述1
题目描述2
题目描述3
题目描述3

解题要点

……题目说可以用贪心策略,暂时还没接触。
直接撸了整个解析文档树

解析时需要用到递归或stack,我这里采用了stack。
层级的处理上,
如果解析到下一个元素层级比当前多1,则跟随push增加层级。
如果解析到下一个元素层级小于当前元素,则证明当前元素已没有更深的子元素,pop直到得到下一个元素的父元素,照常处理。
如果解析到下一个元素层级比当前大于1,证明文档有问题,此处题目保证输入正确其实并不会出现此情况。
需要注意的是,标签名大小写不敏感,因此需要统一转换大小写。

匹配上我用了继承多态+工厂模式,在树上进行遍历查找。
树的遍历查找上也是没有使用递归,而用了stack。
TwoGrandChildSelector是2级选择器,GrandChildSelector是无限级选择器
由于最后证明无限级写对了,所以统一交给无限级处理了,并没有调用2级的
自己写的时候如果感觉无限级没有把握,可以优先把2级的交给TwoGrandChildSelector处理
if (g.size() >= 2)拆成>2==2,把==2交给TwoGrandChildSelector)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iterator>
#include <cctype>
using namespace std;

struct Element {
string tagname;
string id;
int depth;
int line;
Element* parent;
vector<Element*> childs;
};
struct Selector {
virtual bool match(Element* elem) = 0;
};
struct SimpleSelector:Selector {};
struct ComplexSelector :Selector {};
struct TagSelector:SimpleSelector {
string tagname;
bool match(Element* elem) {
return tagname == elem->tagname;
}
};
struct IDSelector:SimpleSelector {
string id;
bool match(Element* elem) {
return id == elem->id;
}
};
struct TwoGrandChildSelector :ComplexSelector {
SimpleSelector* firstSel;
SimpleSelector* secondSel;
bool match(Element* elem) {
if (!secondSel->match(elem)) {
return false;
}
Element* e = elem->parent;
while (e != nullptr) {
if (firstSel->match(e)) {
return true;
}
e = e->parent;
}
return false;
}
};
struct GrandChildSelector :ComplexSelector {
vector<SimpleSelector*> Sels;
bool match(Element* elem) {
if (Sels.empty()) { return false; }
reverse_iterator<vector<SimpleSelector*>::const_iterator> it = Sels.crbegin();
if (!(*it)->match(elem)) {
return false;
}
it++;
while (it != Sels.crend()) {
Element* e = elem->parent;
while (e != nullptr) {
if ((*it)->match(e)) {
elem = e;
break; // 匹配下一个Selector
}
e = e->parent;
}
if (e == nullptr) {
return false; // 此Selector匹配失败
}
it++;
}
return true;
}
};
SimpleSelector* createSimpleSelector(string sel) {
if (sel.size() <= 0) {
return nullptr;
}
if (sel[0] == '#') {
auto s = new IDSelector();
s->id = sel.substr(1);
return s;
}
else {
auto s = new TagSelector();
s->tagname = sel;
transform(s->tagname.begin(), s->tagname.end(), s->tagname.begin(), ::toupper);
return s;
}
return nullptr;
}
ComplexSelector* createComplexSelector(string sel) {
if (sel.size() <= 0) {
return nullptr;
}
vector<string> g;
string::size_type last = 0;
string::size_type space = sel.find(' ');
while (space != string::npos) {
g.push_back(sel.substr(last, space-last));
last = space + 1;
space = sel.find(' ', last);
}
g.push_back(sel.substr(last));
if (g.size() >= 2) {
auto s = new GrandChildSelector();
for (auto & subSel : g) {
s->Sels.push_back(createSimpleSelector(subSel));
}
return s;
}
return nullptr;
}
Selector* createSelector(string sel) {
Selector* r = createComplexSelector(sel);
if (r == nullptr) {
r = createSimpleSelector(sel);
}
return r;
}
struct SelectResult{
SelectResult() :
Count(0), Lines()
{}
int Count;
vector<int> Lines;
};

SelectResult select(Selector* sel, Element* root) {
SelectResult result;
if (sel->match(root)) {
result.Count = 1;
result.Lines.push_back(root->line);
}
for (auto c:root->childs) {
SelectResult subResult = select(sel, c);
result.Count += subResult.Count;
result.Lines.insert(result.Lines.end(), subResult.Lines.cbegin(), subResult.Lines.cend());
}
sort(result.Lines.begin(), result.Lines.end());
return result;
}

// TODO: How to free
Element* parseElementFromS(string s) {
auto elem = new Element();
auto contentI = s.find_first_not_of('.');
auto contentEnd = s.find_first_of(' ', contentI);
auto other = s.find_first_of('#', contentEnd);
if (other == string::npos) {
elem->tagname = s.substr(contentI);
elem->id = "";
}
else {
elem->tagname = s.substr(contentI, contentEnd-contentI);
elem->id = s.substr(other+1);
}
transform(elem->tagname.cbegin(), elem->tagname.cend(), elem->tagname.begin(), ::toupper);
elem->depth = contentI / 2;
return elem;
}

int main()
{
int n, m; cin >> n >> m; cin.get();
Element* root = nullptr;
stack<Element*> chain; // stackDepth = stack.size()-1
for (int i = 0; i < n; i++) {
string s; getline(cin, s);
Element* elem = parseElementFromS(s);
elem->line = i+1;
if (chain.empty()) {
root = elem;
elem->parent = nullptr;
chain.push(elem);
}
else {
int chainDepth = chain.size() - 1;
if (elem->depth > chainDepth + 1) {
return -1;
}
while (elem->depth <= chainDepth) {
chain.pop();
chainDepth--;
}
elem->parent = chain.top();
chain.top()->childs.push_back(elem);
chain.push(elem);
}
}
for (int i = 0; i < m; i++) {
string sel; getline(cin, sel);
auto selector = createSelector(sel);
auto s = select(selector, root);
cout << s.Count;
for (auto l : s.Lines) {
cout << " " << l ;
}
cout << endl;
}
return 0;
}