[csp-201809-3]元素选择器-编译原理

声明：同样是参考照抄hyh学长的代码！（有问题我马上删这篇emm

题目链接：http://118.190.20.162/view.page?gpid=T77

题面：

这棵树的样子（同样是来自学长的图）

题解：

要解决的两个关键问题：

第一个是语义解析，也就是把树构造出来。这个也是用指针实现。这个树的构建比起上一题来更简单，因为节点实际上都是一样的，而上一题（JSON查询）则要分为对象和字符串两种。

　　这里要注意parent的指向，用一个堆实现查找parent。

第二个是查询。要查询符合条件的路径。这里稍微需要一些思路。

　　如果直接从上往下找，那这个复杂度最坏的情况是n^2的。但是在实际情况中（也是题目给的提示），从后往前找会大大减少情况（可以排除很多情况）。

处理细节很重要呀！同样也要想清楚每个函数的作用！

 #include<bits/stdc++.h>

 using namespace std;

 struct tree

 {

     int id, dots;

     string tag, name;

     tree* parent;

     tree(int id, int dots, string tag, string name): id(id), dots(dots), tag(tag), name(name) ,parent() {}//parent的初始化

 };

 void split(const string &str, vector<string> &out)

 {

     string last;

     last.clear();

     for (int i = ; i < str.size(); i++)

     {

         if(str[i] == ' ')

         {

             out.push_back(last);

             last.clear();

         }

         else last+=str[i];

     }

     out.push_back(last);

 }

 bool equal_ignore_case(const string &a,const string &b)

 {

     if(a.size() != b.size()) return ;

     for(int i = ; i < a.size(); i++)

     {

         if(tolower(a[i]) != tolower(b[i])) return ;

     }

     return ;

 }

 bool apply(string str, tree *t)

 {

     if(str[] == '#') return str == t->name;

     else return equal_ignore_case(str, t->tag);

 }

 int main()

 {

     // freopen("a.in","r",stdin);

     int n,m;

     string line;

     scanf("%d%d",&n,&m);

     getline(cin,line);

     vector<tree *> nodes;

     stack<tree *> sta;

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

     {

         getline(cin, line);

         int dots=;

         while (line[dots] == '.') dots++;

         string tag, name;

         stringstream ss(line.substr(dots));

         ss >> tag >> name;

         tree *now = new tree(i, dots, tag, name);

         if(!sta.empty())

         {

             tree* top;

             while (top = sta.top(), top->dots >= dots)

                 sta.pop();

             now->parent = top;

         }

         sta.push(now);

         nodes.push_back(now);

     }

     /*

     for(int i = 0; i < nodes.size(); i++)

     {

         printf("id = %d  dots = %d ",nodes[i]->id,nodes[i]->dots);

         cout << "tag = " << nodes[i]->tag << " name = " << nodes[i]->name ;

         if(nodes[i]->parent) cout << " parent = " << nodes[i]->parent->id << endl;

         else cout << endl;

     }

     */

     vector<string> selector;

     vector<int> ans;

     ans.clear();

     while (m--)

     {

         getline(cin, line);

         selector.clear();

         split(line, selector);

         // printf("************* m = %d\n",m);

         // for(int i = 0 ; i < selector.size(); i++)

             // cout << selector[i] << endl;

         ans.clear();

         for (int i = ; i < nodes.size(); i++)

         {

             if (apply(selector.back(),nodes[i]))

             {

                 tree *t = nodes[i];

                 int sl = selector.size()-;

                 while(t && sl>=)

                 {

                     if(apply(selector[sl],t)) sl--;

                     t = t->parent;

                 }

                 if (sl == -)

                     ans.push_back(nodes[i]->id);

             }

         }

         printf("%d ",ans.size());

         for (int i = ; i < ans.size() ; i++)

             printf("%d ",ans[i]);

         printf("\n");

     }

     return ;

 }

更新一下代码（刷题的时候又遇到了这题，重新做了一遍（并没有什么区别..写码习惯不同））

 #include<bits/stdc++.h>

 using namespace std;

 struct tree{

     string tag,name;

     int dots;

     tree* parent;

     tree(int dots, string tag, string name): dots(dots),tag(tag),name(name),parent() {}

 };

 bool check(const string &s,tree* t)

 {

     if(s[]=='#') return s == t->name;

     else

     {

         if(s.size()!=t->tag.size()) return ;

         for(int i=;i<s.size();i++)

         {

             if(tolower(s[i])!=tolower(t->tag[i])) return ;

         }

         return ;

     }

 }

 void divide(const string &s,vector<string> &vec)

 {

     string token;

     token.clear();

     vec.clear();

     for(int i=;i<s.size();i++)

     {

         if(s[i]==' ')

         {

             vec.push_back(token);

             token.clear();

         }

         else token+=s[i];

     }

     vec.push_back(token);

 }

 int main()

 {

     //freopen("a.in","r",stdin);

     int n,m;

     scanf("%d%d",&n,&m);

     string line;

     getline(cin,line);

     vector<tree* > nodes;

     nodes.clear();

     stack<tree* > sta;

     while(!sta.empty()) sta.pop();

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

     {

         getline(cin,line);

         int dots=;

         while(line[dots]=='.') dots++;

         string tag,name;

         stringstream ss(line.substr(dots));

         ss >> tag >> name;

         tree* now = new tree(dots, tag, name);

         if(!sta.empty())

         {

             tree* top;

             while( top = sta.top() , top->dots >= dots )

                 sta.pop();

             now->parent = top;

         }

         sta.push(now);

         nodes.push_back(now);

     }

     // for(int i=0;i<nodes.size();i++)

     // {

         // cout << "id = " << i << " tag = " << nodes[i]->tag << " name = " << nodes[i]->name ;

         // if(nodes[i]->parent) cout<< " parent = " << nodes[i]->parent->tag;

         // cout << endl;

     // }

     vector<string> sel;

     vector<int> ans;

     while(m--)

     {

         getline(cin,line);

         divide(line,sel);

         ans.clear();

         for(int i=;i<nodes.size();i++)

         {

             int sl=sel.size()-;

             if(check(sel[sl],nodes[i]))

             {

                 tree* t=nodes[i]->parent;

                 sl--;

                 while(t && sl>=)

                 {

                     if(check(sel[sl],t)) sl--;

                     t=t->parent;

                 }

                 if(sl==-) ans.push_back(i+);

             }

         }

         printf("%d ",ans.size());

         for(int i=;i<ans.size();i++) printf("%d ",ans[i]);printf("\n");

     }

     return ;

 }

巴特西

[csp-201809-3]元素选择器-编译原理

最新文章

热门文章