欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

元素选择器

程序员文章站 2022-07-12 16:50:05
...

元素选择器
思路:用树存储数据,每个节点保存元素element,id,father,和son们。
记录上一行有多少个点,计算得到这一行和上一行点的差数/2,就知道要往上走几层(后者直接往下走一层)。
查树阶段。一是查Id,直接遍历树并判断即可。
二是查元素,也是遍历查找即可,元素有可能嵌套。把查找的一串元素(比如:div div p)记录下来,在查找的递归函数中加入一个index,代表当前差的是第几个元素。


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

struct TreeNode
{
	int lineNumber;
	string element;
	string id;
	TreeNode* father = nullptr;
	vector<TreeNode*> son;
	TreeNode(int ln) :lineNumber(ln) {}
};

class Tree
{
public:
	Tree(TreeNode* r) :root(r) {}
	~Tree()
	{
		_erase(root);
	}
	void findById(string id)
	{
		ans.clear();
		_findById(id, root);
		cout << ans.size() << ' ';
		for (auto c : ans) cout << c << ' ';
		cout << '\n';
	}
	void findByElement(vector<string> theElements)
	{
		ans.clear();
		elements = theElements;
		_findByElement(root, 0);
		cout << ans.size() << ' ';
		for (auto c : ans) cout << c << ' ';
		cout << '\n';
	}
private:
	TreeNode* root;
	vector<string> elements;
	vector<int> ans;
	void _erase(TreeNode* curNode)
	{
		if (!curNode) return;
		for (auto c : curNode->son)
			_erase(c);
		delete curNode;
	}
	void _findById(string id, TreeNode* curNode)
	{
		if (!curNode) return;
		if (curNode->id == id) ans.push_back(curNode->lineNumber);
		for (auto c : curNode->son)
			_findById(id, c);
	}
	
	void _findByElement(TreeNode* curNode, int index)
	{
		if (!curNode) return;
		if (curNode->element == elements[index])
		{
			if (index == elements.size() - 1)
				ans.push_back(curNode->lineNumber);
			else
			{
				for (auto c : curNode->son)
					_findByElement(c, index + 1);
			}
		}
		for (auto c : curNode->son)
			_findByElement(c, index);
	}

	void _findByElement2(TreeNode* curNode, int index)
	{
		if (index == elements.size()) ans.push_back(curNode->lineNumber);
		for (auto c : curNode->son)
			if (c->element == elements[index])
			{
				if (index == elements.size() - 1)
					ans.push_back(c->lineNumber);
				else _findByElement2(c, 2);
			}
	}
};


int main()
{
	int n, m; cin >> n >> m;
	TreeNode* root = new TreeNode(1);
	root->element = "html";
	Tree tree(root);
	TreeNode* curNode = root;
	int lastPointNumber = 0;
	getchar();
	string tmp; getline(cin, tmp);
	for (int i = 2; i <= n; i++)
	{
		getline(cin, tmp);
		TreeNode* newNode = new TreeNode(i);
		char c;
		int pointNumber = 0;
		int index = 0;
		for (; tmp[index] == '.'; index++)
			pointNumber++;
		if (pointNumber <= lastPointNumber)
		{
			int layer = (lastPointNumber - pointNumber) / 2 + 1;
			while (layer--)
				curNode = curNode->father;
		}
		curNode->son.push_back(newNode);
		newNode->father = curNode;
		int index2 = index + 1;
		for (; index2 < tmp.size() && tmp[index2] != ' '; index2++);
		newNode->element = tmp.substr(index, index2 - index);
		if (tmp.size() > index2 + 2)
			newNode->id = tmp.substr(index2 + 2);
		lastPointNumber = pointNumber;
		curNode = newNode;
	}
	for (int i = 0; i < m; i++)
	{
		string str;
		getline(cin, str);
		if (str[0] == '#')
			tree.findById(str.substr(1));
		else
		{
			vector<string> elements;
			istringstream in(str);
			string tmp;
			while (in >> tmp) elements.push_back(tmp);
			tree.findByElement(elements);
		}
	}
}
相关标签: 程序设计课