这道题当时考ccf,五道题中做的时间最长的一道题....可惜最好只有0分!!
后来重现写了一下--(110行超级麻烦
主要思想:就是先对括号经行匹配,创建的时候分为创建表和创建元素两种情况,难点在于对字符串的分割
然而昨天在受到某婷的启发下,想用正则重写,发现正则不能实现递归括号匹配,最后用递归的方法重写了这道题.发现超级简单
只有50行....hh
递归版本:
1 #include <bits/stdc++.h> 2 using namespace std; 3 map <string,string> mapp; 4 map <string,int> cls; 5 string str; int pos; 6 string get_name () { 7 string ans; 8 for (pos+=1;str[pos]!='"';pos++) { 9 if (str[pos]=='\') pos++; 10 ans.push_back(str[pos]); 11 } 12 return ans; 13 } 14 void build (string _name) { 15 while (pos<str.size()&&str[pos]!='}') { // 不加pos<str.size()莫名错误90 16 pos++; 17 string s1=get_name(); cls[_name+s1]=2; 18 pos+=2; 19 if (str[pos]=='"') { 20 string s2=get_name(); 21 mapp[_name+s1]=s2; 22 cls[_name+s1]=1; 23 } 24 else build(_name+s1+"."); 25 pos++; 26 } 27 return ; 28 } 29 int main () 30 { 31 int n,m; cin>>n>>m; getchar(); 32 while (n--) { 33 string tmp; getline (cin,tmp); 34 str+=tmp; 35 } 36 string tmp=str; str=""; 37 for (int i=0;i<tmp.size();i++) { 38 if (tmp[i]==' ') continue; 39 str.push_back(tmp[i]); 40 } 41 build (""); 42 while (m--) { 43 getline (cin,tmp); 44 if (cls[tmp]==0) cout<<"NOTEXIST "; 45 else if (cls[tmp]==2) cout<<"OBJECT "; 46 else cout<<"STRING "<<mapp[tmp]<<" "; 47 } 48 return 0; 49 }
复杂版本:
1 // 这个是一个只考虑了简单情况的程序 2 // 关键词字符串包含'{' ,',' ,':'都没有包含 3 #include <bits/stdc++.h> 4 #define none string::npos 5 using namespace std; 6 struct node { 7 string na; 8 int key; 9 string id; 10 }; 11 vector < vector <node> > g(1007); int cnt; 12 vector < string > sv; 13 int mp [10007]; 14 int n,m; 15 string trans(string str) { 16 int x=str.find("""); 17 int y=str.rfind("""); 18 str=str.substr(x+1,y-x-1); string ans; 19 for (int i=0;i<str.size();i++) { //要考虑这样的情况不能直接替换 abc\\sx 20 if (str[i]=='\') { 21 if (str[i+1]=='\') ans+='\'; 22 else ans+='"'; 23 i+=1; 24 } 25 else ans+=str[i]; 26 } 27 return ans; 28 } 29 vector <string> split (const string& str,const char flag=' ') { 30 vector <string> sv; string tmp; 31 istringstream iss(str); 32 while (getline(iss,tmp,flag)) 33 sv.push_back(tmp); 34 return sv; 35 } 36 void match (string str) { 37 stack <int> st; 38 for (int i=0;i<str.size();i++) 39 if (str[i]=='{') st.push(i); 40 else if (str[i]=='}') { 41 mp[st.top()]=i; 42 st.pop(); 43 } // 找到大括号对应的位置 44 } 45 node ct_nt (int start,string str); 46 int ct_obj (int start,string str); 47 bool _find (int k,int x) { 48 if (x==0) return 0; 49 for (int i=0;i<g[x].size();i++) { 50 if (g[x][i].na==sv[k]) { 51 if (k==sv.size()-1) { 52 if (g[x][i].key==0) cout<<"STRING "<<g[x][i].id<<endl; 53 else cout<<"OBJECT"<<endl; 54 return 1; 55 } 56 else 57 return _find(k+1,g[x][i].key); 58 } 59 } 60 return 0; 61 } 62 int main () 63 { 64 cin>>n>>m; getchar(); 65 string str,s1; 66 for (int i=0;i<n;i++) { 67 getline(cin,s1); 68 str+=s1; 69 } 70 match (str); 71 ct_obj(0,str); 72 while (m--) { 73 getline(cin,str); 74 sv=split(str,'.'); 75 if (!_find(0,1)) cout<<"NOTEXIST"<<endl; 76 } 77 return 0; 78 } 79 node ct_nt (int start,string str) { 80 node ans; 81 int k=str.find(":"); 82 string s1=str.substr(0,k); 83 string s2=str.substr(k+1); 84 ans.na=trans(s1); 85 int p=s2.find("{"); 86 if (p==none) {// string 类 87 ans.key=0; 88 ans.id=trans(s2); 89 } 90 else ans.key=ct_obj(start+k+1,s2); 91 return ans; 92 } 93 int ct_obj (int start,string str) { 94 int num=++cnt; 95 int xpos=str.find("{"); 96 int ypos=str.rfind("}"); 97 str[ypos]=','; 98 int i=xpos+1; int p; 99 while ( (p=str.find(",",i))!=none ) { 100 int k=str.find("{",i); 101 if (k!=none&&k<p) { 102 k=mp[start+k]; 103 k=str.find(",",k-start); 104 } 105 else k=p; 106 if (str.substr(i,k-i)!="") { 107 node tmp=ct_nt(start+i,str.substr(i,k-i)); 108 g[num].push_back(tmp); 109 } 110 i=k+1; 111 } 112 return num; 113 } 114