这道题当时考ccf,五道题中做的时间最长的一道题....可惜最好只有0分!!
后来重现写了一下--(110行超级麻烦
主要思想:就是先对括号经行匹配,创建的时候分为创建表和创建元素两种情况,难点在于对字符串的分割
然而昨天在受到某婷的启发下,想用正则重写,发现正则不能实现递归括号匹配,最后用递归的方法重写了这道题.发现超级简单
只有50行....hh
递归版本:
#include <bits/stdc++.h>
using namespace std;
map <string,string> mapp;
map <string,int> cls;
string str; int pos;
string get_name () {
string ans;
for (pos+=;str[pos]!='\"';pos++) {
if (str[pos]=='\\') pos++;
ans.push_back(str[pos]);
}
return ans;
}
void build (string _name) {
while (pos<str.size()&&str[pos]!='}') { // 不加pos<str.size()莫名错误90
pos++;
string s1=get_name(); cls[_name+s1]=;
pos+=;
if (str[pos]=='\"') {
string s2=get_name();
mapp[_name+s1]=s2;
cls[_name+s1]=;
}
else build(_name+s1+".");
pos++;
}
return ;
}
int main ()
{
int n,m; cin>>n>>m; getchar();
while (n--) {
string tmp; getline (cin,tmp);
str+=tmp;
}
string tmp=str; str="";
for (int i=;i<tmp.size();i++) {
if (tmp[i]==' ') continue;
str.push_back(tmp[i]);
}
build ("");
while (m--) {
getline (cin,tmp);
if (cls[tmp]==) cout<<"NOTEXIST\n";
else if (cls[tmp]==) cout<<"OBJECT\n";
else cout<<"STRING "<<mapp[tmp]<<"\n";
}
return ;
}
复杂版本:
// 这个是一个只考虑了简单情况的程序
// 关键词字符串包含'{' ,',' ,':'都没有包含
#include <bits/stdc++.h>
#define none string::npos
using namespace std;
struct node {
string na;
int key;
string id;
};
vector < vector <node> > g(); int cnt;
vector < string > sv;
int mp [];
int n,m;
string trans(string str) {
int x=str.find("\"");
int y=str.rfind("\"");
str=str.substr(x+,y-x-); string ans;
for (int i=;i<str.size();i++) { //要考虑这样的情况不能直接替换 abc\\\\sx
if (str[i]=='\\') {
if (str[i+]=='\\') ans+='\\';
else ans+='\"';
i+=;
}
else ans+=str[i];
}
return ans;
}
vector <string> split (const string& str,const char flag=' ') {
vector <string> sv; string tmp;
istringstream iss(str);
while (getline(iss,tmp,flag))
sv.push_back(tmp);
return sv;
}
void match (string str) {
stack <int> st;
for (int i=;i<str.size();i++)
if (str[i]=='{') st.push(i);
else if (str[i]=='}') {
mp[st.top()]=i;
st.pop();
} // 找到大括号对应的位置
}
node ct_nt (int start,string str);
int ct_obj (int start,string str);
bool _find (int k,int x) {
if (x==) return ;
for (int i=;i<g[x].size();i++) {
if (g[x][i].na==sv[k]) {
if (k==sv.size()-) {
if (g[x][i].key==) cout<<"STRING "<<g[x][i].id<<endl;
else cout<<"OBJECT"<<endl;
return ;
}
else
return _find(k+,g[x][i].key);
}
}
return ;
}
int main ()
{
cin>>n>>m; getchar();
string str,s1;
for (int i=;i<n;i++) {
getline(cin,s1);
str+=s1;
}
match (str);
ct_obj(,str);
while (m--) {
getline(cin,str);
sv=split(str,'.');
if (!_find(,)) cout<<"NOTEXIST"<<endl;
}
return ;
}
node ct_nt (int start,string str) {
node ans;
int k=str.find(":");
string s1=str.substr(,k);
string s2=str.substr(k+);
ans.na=trans(s1);
int p=s2.find("{");
if (p==none) {// string 类
ans.key=;
ans.id=trans(s2);
}
else ans.key=ct_obj(start+k+,s2);
return ans;
}
int ct_obj (int start,string str) {
int num=++cnt;
int xpos=str.find("{");
int ypos=str.rfind("}");
str[ypos]=',';
int i=xpos+; int p;
while ( (p=str.find(",",i))!=none ) {
int k=str.find("{",i);
if (k!=none&&k<p) {
k=mp[start+k];
k=str.find(",",k-start);
}
else k=p;
if (str.substr(i,k-i)!="") {
node tmp=ct_nt(start+i,str.substr(i,k-i));
g[num].push_back(tmp);
}
i=k+;
}
return num;
}