CCF201809-3 元素选择器

题目主干

解题要点

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

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

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

代码示例

#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;
}

Donate