AcWing 3249. JSON查询
原题链接
中等
作者:
自由的犇儿哥
,
2021-08-26 14:12:44
,
所有人可见
,
阅读 390
这种方法在csp官方网站上得到了满分,但是却无法通过ACwing上的最后一个数据,大家批评指正
- 主要的思想就是通过递归的方式,一层一层地处理大括号里的数据。并维护map表
- 猜测是数据的键值对中含有冒号和花括号,导致我无法正确划分键值对范围
#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
#include <stack>
#include <cmath>
#include <cstring>
#include <stack>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
using namespace std;
#define MAX 0x3f3f3f3f
map<string, string> da;
string json;
string dealvalue(string str)
{
string ans;
for (int i = 1; i < str.size() - 1; i)
{
if (str[i] == '\\' && str[i + 1] == '\\')
{
ans += "\\";
i += 2;
}
else if (str[i] == '\\' && str[i + 1] != '\\')
{
i++;
}
else
{
ans += str[i];
i++;
}
}
return ans;
}
void dealjson(string pre, int l, int r)
{
int tl = l + 1, tr = l + 1;
while (tr < r)
{
int colon = 0;
while (tr < r && json[tr] != ':')
{
tr++;
}
if (json[tr + 1] == '{')
{ //如果是对象的话
int rem = tr + 1; //记住第一次出现的左括号
int brcnt = 0;
tr++;
while (tr < r)
{
if (json[tr] == '{')
brcnt++;
else if (json[tr] == '}')
brcnt--;
tr++;
if (brcnt == 0)
break;
}
string item = json.substr(tl, tr - tl);
int loc = item.find(":");
string name = dealvalue(item.substr(0, loc));
if (pre == "")
{
da[name] = "OBJECT";
dealjson(name, rem, tr - 1);
}
else
{
da[pre + "." + name] = "OBJECT";
dealjson(pre + "." + name, rem, tr - 1);
}
tl = tr + 1;
tr++;
}
else
{
while (tr < r)
{
tr++;
if (tr >= r || (json[tr] == ',' && json[tr - 1] == '\"' && json[tr + 1] == '\"'))
break;
}
string item = json.substr(tl, tr - tl);
int loc = item.find(":");
string name = dealvalue(item.substr(0, loc));
string value = dealvalue(item.substr(loc + 1));
if (pre.empty())
{
da[name] = value;
}
else
{
da[pre + "." + name] = value;
}
tl = tr + 1;
tr++;
}
}
}
int main()
{
freopen("sb.txt", "r", stdin);
//这里有m个输入
int n, m;
cin >> n >> m;
int l = 0;
stack<string> st;
getchar();
for (int i = 0; i < n; i++)
{
string str;
getline(cin, str);
stringstream sou(str);
string t;
// cout << str << endl;
while (sou >> t)
{
json += t;
}
}
// cout << json << endl;
dealjson("", 0, json.size() - 1);
while (m--)
{
string search;
cin >> search;
if (da.count(search) == 0)
cout << "NOTEXIST" << endl;
else
{
auto ans = da[search];
if (ans == "OBJECT")
{
cout << ans << endl;
}
else
{
cout << "STRING"
<< " " << ans << endl;
}
}
}
return 0;
}