[csp-201709-3]JSON查询-编译原理

声明：这个代码几乎完全就是照抄hyh学长的！！！

有什么问题我会删掉这篇的emm

当初面试的时候我的方向就是编译原理...然后学长发了个1400+的代码实现一个简化的c编译器...没看懂qaq

感觉很多知识还是很缺失的emm（当初连高维数组是怎么存的都不知道啊！指针几乎完全不会用啊！更别说什么函数怎么层层递归变量怎么层层声明的）现在总算是懂了JSON这个呀越发觉得这个代码写得很美妙啊hhh

先发一下题面：

题意：

一段JSON结构的代码

一种是字符串名称-键值 “ ” : “ ”

一种是对象（有对象名）{}

对象里面可以是多个字符串，或者是嵌套的对象。

题解：

应该算是很典型的编译原理类题目吧

这个层层嵌套的对象怎么实现呢？其实是定义一个object类型，然后用每个对象用指针指向，一层层嵌套。有这个大概的想法可能不难，难点应该是在于这个代码怎么实现。

这个也是提醒我打之前要想好每个函数的作用，要准确清晰，不然会越打越混乱，无限debug。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 string json;
  5 string::iterator ptr;
  6 
  7 struct obj
  8 {
  9     map<string, obj *> child;
 10     
 11     string value;
 12     
 13     bool is_obj;
 14     
 15     obj() : is_obj(true) {}
 16     obj(const string &value) : value(value),is_obj(false) {} //初始化，调用obj(value)时的赋值 
 17 };
 18 
 19 void skip_non_blank_char()
 20 {
 21     while(isspace(*ptr)) ptr++;
 22     //isspace(char) distinguish空格/回车/制表符等
 23 }
 24 
 25 char peek_char()
 26 {
 27     skip_non_blank_char();
 28     return *ptr;
 29 }
 30 
 31 char next_char()
 32 {
 33     skip_non_blank_char();
 34     return *ptr++;
 35     //*ptr++：是先取出*ptr的值，再使ptr加1
 36 }
 37 
 38 string parse_string()
 39 {
 40     next_char(); // "
 41     char c;
 42     bool escape = 0; //转义字符 escape char
 43     string token;
 44     while(c = next_char(),1)
 45     {
 46         if(!escape)
 47         {
 48             if(c == '"') break;
 49             if(c == '\') 
 50             {
 51                 escape = true;
 52                 continue;
 53             }
 54         }
 55         else escape = 0;
 56         token += c;
 57     }
 58     return token;
 59 }
 60 
 61 obj* parse_value()
 62 {
 63     if (peek_char() == '{') // an object
 64     {
 65         next_char();
 66         
 67         obj* res = new obj();
 68         
 69         while(1)
 70         {
 71             if (peek_char() != '"') break;
 72             string key = parse_string();
 73             next_char(); // :
 74             obj* val = parse_value();
 75             res->child[key] = val;
 76             if(peek_char() == '}') break;
 77             next_char(); // ,
 78         }
 79         
 80         next_char(); // }
 81         return res;
 82     }
 83     else 
 84     {
 85         obj* res = new obj(parse_string());
 86         return res;
 87     }
 88 }
 89 
 90 int main()
 91 {
 92     // freopen("a.in","r",stdin);
 93     int n,q;
 94     string line;
 95     scanf("%d%d",&n,&q);
 96     getline(cin,line);
 97     json.clear();
 98     for (int i = 1; i <= n; i++)
 99     {
100         getline(cin,line);
101         json+=line;
102     }
103     ptr = json.begin();
104     obj* root = parse_value();
105     
106     
107     
108     while (q--)
109     {
110         getline(cin,line);
111         
112         obj* cur = root;
113         string t;
114         t.clear();
115         bool not_found = 0;
116         for (int i = 0; i <= line.size() ; i++)
117         {
118             if (i == line.size() || line[i] == '.')
119             {
120                 if (!cur->child.count(t))
121                 {
122                     not_found = 1;
123                     break;
124                 }
125                 cur = cur->child[t];
126                 t.clear();
127             }
128             else t += line[i];
129         }
130         
131         if (not_found) cout << "NOTEXIST" << endl;
132         else if (cur->is_obj) cout << "OBJECT" << endl;
133         else cout << "STRING " << cur->value << endl;
134         
135     }
136     return 0;
137 }