Hierarchical Notation(2014 Regional 牡丹江)

题目

Hierarchical Notation

题目大意

解析一个EON格式的字符串,然后查询内容。

解题思路

EON格式是树状结构。扫描字符串,根据状态转换解析各个node。

我的代码

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

#define T_KEY 0
#define T_VALUE 1
#define T_ARRAY 2

struct Node
{
int st;
int ed;
int type;
Node* ft;
vector<Node*> lt;
}*root;

const char* pjson;

void parse(const string& json)
{

root = new Node();
root->st = 0;
root->ed = 0;
Node* now = root;
Node* lastS = NULL;
stack<Node*> Qdb;
int flag = 0; //标记""内外
int p = 0;
while(p<json.size())
{
if(json[p] == '{')
{
Node* t = new Node();
t->st = p;
t->ft = now;
Qdb.push(t);
t->type = T_ARRAY;
now->lt.push_back(t);
now = t;
}
if(json[p] == '}')
{
Qdb.top()->ed = p;
Qdb.pop();
if(!Qdb.empty())
now = Qdb.top();
}
if(json[p] == ':')
{
now = lastS;
}
if(json[p] == '\"')
{
if(flag) //string结束
{
lastS->ed = p;
if(lastS->type == T_VALUE)
now = now->ft;
flag = 0;
}
else //string开始
{
Node* t = new Node();
lastS = t;
t->st = p;
t->ft = now;
if(now->type == T_KEY)
t->type = T_VALUE;
else
t->type = T_KEY;
now->lt.push_back(t);
flag = 1;
}
}
++p;
}
}

Node* findNode(Node* now, const string& key)
{

for(int i=0; i<now->lt.size(); ++i)
{
if(now->lt[i]->type == T_ARRAY)
{
Node* t = findNode(now->lt[i],key);
if(t != NULL)
return t;
}
if(now->lt[i]->type == T_KEY)
{
if(!strncmp(key.c_str(), pjson+now->lt[i]->st, key.size()))
return now->lt[i];
}
}
return NULL;
}

string query(const string& json, const string& q)
{

Node* now = root;
int flag = 0;
int p = 0;
int st = 0;
while(p < q.size())
{
if (q[p] == '\"')
{
if (flag) //string结束
{
now = findNode(now, q.substr(st, p - st + 1));
if (now == NULL)
return "Error!";
flag = 0;
}
else //string开始
{
st = p;
flag = 1;
}
}
++p;
}
return json.substr(now->lt[0]->st, now->lt[0]->ed - now->lt[0]->st + 1);
}

void clear(Node* now)
{

for(int i=0; i<now->lt.size(); ++i)
{
clear(now->lt[i]);
}
clear(now);
}

int main()
{

int T;
cin >> T;
while(T--)
{
string json;
cin >> json;
pjson = json.c_str();
parse(json);
//db(json, root->lt[0]);
int Q;
cin >> Q;
while(Q--)
{
string key;
cin >> key;
cout << query(json,key) << endl;
}
}
}
/*
1
{"a":{"b":"b","f":{"c":{"a":{"b":"s","v":"k"}},"sdf":"r"}}}

8
"a"
"b"
"b"."b"
"a"."f"
"a"."f"."c"
"a"."f"."c"."a"."b"
"a"."f"."c"."a"."v"
"a"."f"."sdf"
*/