当前位置：网站首页>201709-3 CCF jason查询 （满分题解）

201709-3 CCF jason查询 （满分题解）

2022-08-03 18:27:00 【一只可爱的小猴子】

问题描述

JSON查询题目链接

解题思路

首先将整个对象存储下来，然后根据每个查询进行输出结果
难点在于存储对象，以及解析对象
采用结构体嵌套map的方式存储（可以看代码，结构比较清晰）

实现技巧

这种需要嵌套定义并且类型不一时，可以用变量区分变量类型
结构体里不能嵌套unordered_map,可以嵌套map
对于多个函数操作一个字符串，可以将指针加引用，相当于指针跟着函数的操作移动，不需要再额外增加形参记录当前指针位置
反斜杠需要用//
使用未定义函数需要申明，不需要变量名
在选择结构中，如果该部分代码太长，也拎出来写，这样使得选择结构清晰易读，逻辑清晰
会多次用到的部分，使用函数来表示
不能直接赋值，会出错（该结构体的嵌套结构体赋给该结构体时。。maybe）
erase删除后，字符会左移，原来的下一个字符会变成当前这个字符，处理的时候要考虑到这个问题
答案特判输出时，询问情况应考虑全面

代码实现

条理清晰版

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

//这种需要嵌套定义并且类型不一时，可以用变量记录变量类型
struct Obj
{
    
    int type; //1为str， 2为obj
    string str;
    Obj(){
    }
    Obj(string t)
    {
    
        type = 1;
        str = t;
    }
    //结构体里不能嵌套unordered_map,可以嵌套map
    map <string, Obj> kv; //对象中的key-value对
};

//会多次用到的部分，使用函数来表示
string work_str(string &str, int &pos)
{
    
    pos ++; //滤过'"'
    string s;
    while (pos < str.size() && str[pos] != '\"')
    {
    
        if (str[pos] == '\\') s += str[pos + 1], pos += 2; //反斜杠需要用//
        else s += str[pos ++];
    }
    pos ++; //滤过'"'
    return s;
}

//使用前需要申明，不需要变量名
Obj work_obj(string &, int &);

//在选择结构中，如果该部分代码太长，也拎出来写，这样使得选择结构清晰易读，逻辑清晰
void work_kv(Obj &thisobj, string &str, int &pos)
{
    
    string key = work_str(str, pos);
    pos = str.find(':', pos); //找到':'位置
    while (str[pos] != '\"' && str[pos] != '{') pos ++;
    if (str[pos] == '\"') thisobj.kv[key] = Obj(work_str(str, pos));
    else thisobj.kv[key] = work_obj(str, pos);
}

Obj work_obj(string &str, int &pos)
{
    
    Obj thisobj;
    thisobj.type = 2;
    while (pos < str.size() && str[pos] != '{') pos ++;
    pos ++; //过滤掉'{'
    while (pos < str.size() && str[pos] != '}')
    {
    
        if (str[pos] == '\"') work_kv(thisobj, str, pos);
        else pos ++;
    }
    pos ++; //滤过'}'
    return thisobj;
}

void query(Obj obj, vector <string> qs)
{
    
    for (auto q : qs)
    {
    
        if (obj.type == 1 || obj.kv.count(q) == 0)
        {
    
            puts("NOTEXIST");
            return ;
        }
        
        // 不能直接赋值，会出错（该结构体的嵌套结构体赋给该结构体时。。maybe）
        Obj t = obj.kv[q];
        obj = t;
    }
    
    if (obj.type == 1) printf("STRING %s\n", obj.str.c_str());
    else puts("OBJECT");
}

int main()
{
    
    int n, m;
    cin >> n >> m;
    getchar();
    
    string str, tmp;
    while (n --)
    {
    
        getline(cin, tmp);
        str += tmp; //将整个对象合并成一个串
    }
    
    int p = 0; //串的起始位置

    auto mainobj = work_obj(str, p); //处理最外层的对象
    
    while (m --)
    {
    
        getline(cin, tmp);
        vector <string> qs; //存储每一个查询
        for (int i = 0; i < tmp.size(); i ++)
        {
    
            int j = i + 1;
            while (j < tmp.size() && tmp[j] != '.') j ++;
            qs.push_back(tmp.substr(i, j - i));
            i = j;
        }
        query(mainobj, qs);
    }
    return 0;
}

递归暴力版

#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>

using namespace std;

vector <unordered_map<string, string>> ALL;

int Loop(string str,int pos) //pos是{的下标，cnt是当前对象存储在vector中的下标，返回当前处理到的字符下标
{
    
    int cnt = 0;
    //cout << "LOOOOOP" << endl;
    unordered_map <string, string> tmap; //当前map
    ALL.push_back(tmap);
    cnt = ALL.size() - 1; //当前存储的下标
    int tcnt = cnt;

    //判断该对象是否为空
    int ed = str.find('}', pos);
    if (ed != -1)
    {
    
        string ob = str.substr(pos, ed - pos + 1);
        if (ob.find('"') == -1) // 当前该对象为空
        {
    
            return ed; //返回}的下标
        }
    }


    //当前对象不为空
    for (int i = pos; i < str.size(); i ++) //从{开始处理
    {
    
        //处理一对键值
        if (str[i] == '}' || str.find('"', i) == -1)
        {
    
            i = str.find('}', i);
            return i;
        }
        string kk = "";
        int j = str.find('"', i) + 1;
        for (; j < str.size(); j ++)
        {
    
            if (int(str[j]) == 92) kk += str[++ j]; //当遇到/，保存后一位
            else if (str[j] == '"') break; //结束
            else kk += str[j];
        }
        //cout << kk << " ";
        //当前值为string
        string vv = "";
        j += 2;
        if (str[j] == '"')
        {
    
            j ++;
            for (; j < str.size(); j ++)
            {
    
                if (int(str[j]) == 92) vv += str[++ j]; //当遇到/，保存后一位
                else if (str[j] == '"') break; //结束
                else vv += str[j];
            }
            //cout << vv << endl;
            ALL[cnt][kk] = vv;
            //cout << kk << " " << ALL[cnt][kk] <<endl;
            i = j;
            i ++;
            //cout << str[i] << endl;
            if (str[i] == '}')
            {
    
                //cout << "bingo" << endl;
                return i; //返回}的下标
            }
        }
        else //值为对象
        {
    
            //cout << kk << " " << "OBJECT" << endl;
            i = Loop(str,j);
            //cout << str[i] << endl;
            vv += " ";
            vv += to_string(tcnt + 1);
            tcnt ++; //同一个对象中可能包含多个同级对象，所以需要增加
            //cout << kk << " " << vv << endl;
            ALL[cnt][kk] = vv; //当前对象下的键值对，存储键值以及对象的编号
            //cout << kk << " " << ALL[cnt][kk] <<endl;
        }
    }
}

int main()
{
    
    int n, m;
    cin >> n >> m;
    string str = "";
    string tmp = "";
    getchar();
    for (int i = 0 ; i < n; i ++)
    {
    
        getline(cin, tmp);
        str += tmp; //将所有语句合并成一行统一格式
    }
    //erase删除后，字符会左移，原来的下一个字符会变成当前这个字符，处理的时候要考虑到这个问题
    for (int i = 0; i < str.size(); i ++)
    {
    
        while(str[i] == ' ') str.erase(i, 1); //删除所有的空格
        //cout << i << endl;
    }

    //cout << str << endl;

    int cnt = 0;
    int pos = 0;

    pos = Loop(str,pos);

    //cout << endl << endl;
    string q;
    for (int i = 0; i < m; i ++)
    {
    
        getline(cin, q);
        //cout << q << "+++" << endl;
        string tq = "";
        vector <string> qv;
        if (q.find('.') == -1) qv.push_back(q);
        else
        {
    
            for (int j = 0; j < q.size(); j ++) //根据.分割
            {
    
                if (q[j] != '.')
                {
    
                    tq += q[j];
                }
                if (q[j] == '.' || j == q.size() - 1)
                {
    
                    qv.push_back(tq);
                    //cout << tq << endl << endl;
                    tq = "";
                }
            }
            if (tq != "") qv.push_back(tq); //根据某个分隔符进行划分时，注意处理末尾特殊情况
        }

        //答案特判输出时，询问情况考虑全面
        int c = 0;
        for (int j = 0; j < qv.size(); j ++)
        {
    
            if (ALL[c].count(qv[j]) != 0)
            {
    
                //cout << "bingo" << endl;
                string rr = ALL[c][qv[j]];
                if (rr.find(' ') != -1)
                {
    
                    //cout << j << " " << qv.size() - 1 << endl;
                    if (j == qv.size() - 1)
                    {
    
                        cout << "OBJECT" << endl;
                    }
                    else
                    {
    
                        //cout << "next" << endl;
                        rr.erase(0, 1);
                        //cout << c << "->";
                        //将int转换为string
                        c = atoi(rr.c_str());
                        //cout << c << endl;
                        continue;
                    }
                }
                else
                {
    
                    if (j != qv.size() - 1) cout << "NOTEXIST" << endl; //输入格式考虑不够完善
                    else cout << "STRING " << rr << endl;
                    break;
                }
            }
            else
            {
    
                /*for (auto x : ALL[c]) cout <<c << " " << x.first << " " << x.second << endl;*/
                cout << "NOTEXIST" << endl;
                break;
            }
        }
    }
    return 0;
}
原网站

版权声明
本文为[一只可爱的小猴子]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_51800570/article/details/125786858

边栏推荐

猜你喜欢

随机推荐