算法

模拟

题目描述

给出一个文档，里面是HTML标签，要求设计HTML元素选择器

解题思路

定义结构体，存储元素的所有信息
在读入文档的过程中，比较重要的就是如何确定上一级。使用栈并通过点的数量判断层数即可。
读入的时候通过substr截断，截断位置通过#和空格判断。
对于id选择器和标签选择器来说其实很好实现，关键在于后代选择器，并且后代选择器可以出现多个属性。这里使用递归操作，每次找到符合最后一个属性条件的元素，后面的属性在调用本函数判断父元素。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include <vector>
#include <stack>
using namespace std;

string tos(string a) {
    string ans = "";
    for (int i = 0; i < a.length(); i++) {
        if (a[i] >= 'A' && a[i] <= 'Z') {
            ans += a[i] - 'A' + 'a';
        }
        else ans += a[i];
    }
    return ans;
}

struct At
{
    int d;//层数
    string lab;//标签
    string id;//id属性
    At* fa;
    bool find(string s) {
        if (s[0] == '#') {
            s = s.substr(1);//去掉井号
            return id == s;
        }
        else {
            return tos(lab) == tos(s);
        }
    }
    bool findfa(string s) {
        if (s.find(' ') == string::npos) {
            bool ok = 0;
            At* f = fa;
            while (f != NULL && !ok)
            {
                ok = f->find(s);
                f = f->fa;
            }
            return ok;
        }
        else {
            int sub = s.size() - 1;
            while (s[sub] != ' ')   sub--;
            string fax = s.substr(0, sub);
            string xxx = s.substr(sub + 1);
            bool ok = 0;
            At* f = fa;
            while (f != NULL && !ok)
            {
                ok = f->find(xxx)&&f->findfa(fax);
                f = f->fa;
            }
            return ok;
        }

    }
/*
    At(){
        d = 0;
        fls = fis = 0;
    }
*/
}ele[101];//元素




int main() {
    int n, m;
    cin >> n >> m;
    getchar();

    stack<At*> far;

    for (int i = 1; i <= n; i++) {

        string s;
        getline(cin, s);
        int x = 0;
        while (s[x] == '.') x++;
        ele[i].d = x / 2;

        if (s.find('#') != string::npos)//有id属性
        {
            ele[i].id = s.substr(s.find('#') + 1);
            ele[i].lab = tos(s.substr(x, s.find('#') - x - 1));
        }
        else //无id属性
        {
            ele[i].id = "";
            ele[i].lab = tos(s.substr(x));
        }

        ele[i].fa = NULL;
        if (!far.empty())
        {
            At* f = far.top();
            while (f->d >= ele[i].d)
            {
                far.pop();
                f = far.top();
            }
            ele[i].fa = f;
        }
        far.push(&ele[i]);
    }

    int ans[101];
    for (int i = 1; i <= m; i++)
    {
        string s;
        getline(cin, s);
        int anss = 0;
        memset(ans, 0, sizeof ans);
        if (s.find(' ') == string::npos) {
            for (int j = 1; j <= n; j++)
                if (ele[j].find(s))
                    ans[++anss] = j;
            cout << anss << ' ';
            for (int j = 1; j <= anss; j++) cout << ans[j] << ' ';
            cout << endl;
        }
        else {
            int sub = s.size() - 1;
            while (s[sub] != ' ')   sub--;
            string fax = s.substr(0, sub);
            string xxx = s.substr(sub + 1);
            for (int j = 1; j <= n; j++)
                if (ele[j].find(xxx)&&ele[j].findfa(fax)) {
                    ans[++anss] = j;
                }
            cout << anss << ' ';
            for (int j = 1; j <= anss; j++) cout << ans[j] << ' ';
            cout << endl;
        }
    }

    return 0;
}
/*
11 100
html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #none
......div
........p #two
div p
*/

题目总结

一定要仔细仔细仔细读题，题目说标签大小写不敏感而id敏感。注意区分。