• 北京化工大学第17届程序设计竞赛 - 女生赛 - 2022.08.28 - 问题 A: You love JSON. Aren‘t you?

    传送门

    You love JSON. Aren’t you?

    时间限制：1秒
    空间限制：128M

    题目描述

    在这道问题中，你需要按照要求，格式化给定的JSON对象。

    JSON(JavaScript Object Notation)是一种轻量级的数据交换格式。

    为了方便处理，本题的JSON字符串满足以下限制：

    JSON对象具有以下形式：

    {左括号     ,逗号隔开的数个键值对     }右括号

    例如：

    • {}（0个键值对）
    • { }（0个键值对）
    • {键值对}（1个键值对）
    • {键值对,键值对}（2个键值对）
    • {键值对 , 键值对 }（2个键值对）
    • {键值对, 键值对, 键值对}（3个键值对）

    键值对具有以下形式：

    字符串     :     值

    例如：

    • 字符串: 值
    • 字符串 :值

    本题不用考虑多个键值对是否相同的问题

    字符串具有以下形式：

    “双引号     字符串内容     ”双引号

    例如：

    • "字符串内容"

    字符串内容可以包括字母、数字、以及非"字符（本题不需要考虑字符串转义的问题）

    例如：

    • LetMeFly
    • Tisfy
    • Ha?ks_998Ys
    • .;lsfjie:

    值可以是字符串，也可以是JSON对象（此题不考虑数字、布尔值、数组等）

    例如：

    • "LetMeFly"（这是一个字符串）
    • {"LetMeFly": "Tisfy"}（这是一个JSON对象）

    以下都是符合本题题意的JSON对象：

    • {}
    • {"LetMeFly" : "Tisfy"}
    • {"LetMeFly": "Tisfy", "aHa?": "888"}
    • {"LetMeFly" : {"TaoWa?": "Yes!"}}
    • {"____" : {"TaoWa?": {"ZaiLaiYiCeng": "..."}}, "DouHao": "GeKai"}
    • {"ZiFuChuan_string": "FakeJSONObject{"}
    • {"data":{"problemsetStreakCounter":{"today":"2022-08-22T16:04:39.145943197+08:00","streakCount": "399","daysSkipped":"0","todayCompleted":"true","__typename":"StreakCounterNode"}}}
    • {"ZuiHouYiTi?" : "MayBe"}

    到此为止，此题的JSON对象的格式终于讲完了。

    但是需求才刚刚开始😷

    这道题的需求是，给你一个符合上述条件的JSON对象，请你按照要求将其格式化。

    JSON对象格式化后为：

    {左括号
四个空格的缩进   键值对1  逗号
四个空格的缩进   键值对2  逗号
四个空格的缩进   键值对3
}右括号

    • 1
    • 2
    • 3
    • 4
    • 5

    例如：

    {
    键值对1,
    键值对2,
    键值对3
}

    • 1
    • 2
    • 3
    • 4
    • 5

    或者（键值对数量为0）

    {
}

    • 1
    • 2

    空的JSON对象这样格式化好像挺丑的，但是此题就不再要求空的JSON对象要格式化到一行了

    键值对格式化后为：

    字符串 :冒号 一个空格 值

    • 1

    例如

    "LetMeFly": "Tisfy"

    • 1

    或者（值为JSON对象）

    "MaoHaoHouDeKongGeShiJianZhiDuiDeGeShiHuaYaoQiu": {
    "QianMianYaoZaiYou4GeSuoJin": "ZheShiJSONDuiXiangDeGeShiHuaYaoQiu"
}

    • 1
    • 2
    • 3

    以下都是符号要求的格式化后的JSON对象

    {
}

    • 1
    • 2
    {
    "1234567890": "!@#$%^&*()"
}

    • 1
    • 2
    • 3
    {
    "1": "2",
    "3": "4"
}

    • 1
    • 2
    • 3
    • 4
    {
    "1": "2",
    "3": {
        "4": "5"
    },
    "6": "7"
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    {
    "^_^": "^_^",
    "^_^.": {
        "^_^": {
            "^_^": {
                "^_^": "^_^"
            }
        }
    },
    ".^_^": "^_^"
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    输入描述

    输入格式：

    输入为一行一个没有空格的JSON对象字符串，保证数据合法

    数据范围：

    输入字符串的长度不超过2000

    输出描述

    输出按照题目要求格式化后的JSON字符串

    例如：

    {"^_^":"^_^","^_^.":{"^_^":{"^_^":{"^_^":"^_^"}}},".^_^":"^_^"}

    • 1

    ↓

    {
    "^_^": "^_^",
    "^_^.": {
        "^_^": {
            "^_^": {
                "^_^": "^_^"
            }
        }
    },
    ".^_^": "^_^"
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    再例如：

    {"LetMeFly":{"Tisfy":"^_^"},"BeCarefulOfMe:":"TheCharacter'{'IsFake"}

    • 1

    ↓

    {
    "LetMeFly": {
        "Tisfy": "^_^"
    },
    "BeCarefulOfMe:": "TheCharacter'{'IsFake"
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    再例如：

    {"1":"2","3":{"4":"5"},"6":"7"}

    • 1

    ↓

    {
    "1": "2",
    "3": {
        "4": "5"
    },
    "6": "7"
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    再例如：

    {"1":{"2":{"3":{"4":{"5":"6"}}}}}

    • 1

    ↓

    {
    "1": {
        "2": {
            "3": {
                "4": {
                    "5": "6"
                }
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    再例如：

    {"1":{"2":{"3":{"4":"5"}}},"6":"7"}

    • 1

    ↓

    {
    "1": {
        "2": {
            "3": {
                "4": "5"
            }
        }
    },
    "6": "7"
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    再例如：

    {"1":"2","3":{"4":"5"}}

    • 1

    ↓

    {
    "1": "2",
    "3": {
        "4": "5"
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    再例如：

    {"1":{}}

    • 1

    ↓

    {
    "1": {
    }
}

    • 1
    • 2
    • 3
    • 4

    样例一

    输入
    {"LetMeFly":{"Tisfy":"^_^"},"BeCarefulOfMe:":"TheCharacter'{'IsFake"}

    • 1
    输出
    {
    "LetMeFly": {
        "Tisfy": "^_^"
    },
    "BeCarefulOfMe:": "TheCharacter'{'IsFake"
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    题目分析

    这道题我觉得题目描述已经很详细了（自夸一波）

    题目中已经把所有可能出现的情况全部讲出来了，以及可能出现的“坑”等都在样例中出现过。

    因此，我觉得这道题主要在考察细心程度（读题明规则）以及编码能力（规则变实际）

    解题思路

    这道题的解题思路就是“按照规则分析并格式化字符串”

    其实也就两大需要处理的东西：

    1. JSON对象（的左右括号）
    2. 数个键值对

    那么，不如把这些交给两个函数：

    • string formatJSON()用来处理JSON对象的左右大括号
    • string formatKeyValPair()用来处理JSON对象中的数个键值对

    为了方便，我们使用两个变量：

    1. nowIndent用来记录当前处理过程中应有的缩进（键值对全面有几个空格）
    2. nowTo用来记录处理到了字符串的哪个字符（值为下一个该处理的字符的下标）

    实现formatJSON()时：

    首先第一个字符一定是左大括号{

    处理完大括号就该处理键值对了，直接丢给formatKeyValPair()函数来处理。

    等formatKeyValPair()函数处理完后，下一个字符一定是右大括号}

    这样，formatJSON()的使命就这么轻松愉快地完成了。

    至于缩进，处理完左大括号后，缩进+4。

    等formatKeyValPair()函数处理完键值对后，再把缩进-4即可。

    接下来的问题就只剩下“如何处理数个键值对”了

    实现formatKeyValPair()时：

    因为键值对的数量不确定，因此这个函数的终止条件是：遇到右终止大括号}

    这里需要特别注意的是，“遇到右终止大括号}”是指遇到“非字符串中的}字符”，也不是某个键值对的“JSON对象”的值的右大括号。

    在没有遇到右终止大括号的时候，首先会遇到一个字符串，然后会遇到“:”

    之后得看下一个字符是“{”还是“"”。

    • “{”说明“值”是“JSON对象”，那么直接丢给formatJSON()函数来处理
    • “"”说明“值”是“字符串”，那么就自己处理，直到找到下一个“"”为止

    伪代码为:

    string formatKeyValPair() {
    while (s[nowTo] != '}') {
        处理左字符串

        处理“:”

        看“值”的第一个字母
            如果是“"”，就值为“字符串”，直接遍历到下一个“"”为止
            否则，就说明是JSON对象，丢给formatJSON()处理
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    处理完一个键值对后，如果下一个字符是“}”，就说明已无下一个键值对。

    否则说明还有下一个键值对，记得输出逗号再换行。

    AC代码

    代码去掉注释也就100行，还行还行

    #include 
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

class JSONFormatter {
private:
    string s;
    int nowIndent;  // 现在已有的缩进量
    int onceIndent;  // 每次缩进4个空格
    int nowTo;  // 现在处理到了哪个下标

    /*
        格式化JSON对象
        如题，JSON对象的左大括号无需考虑4个空格的缩进问题，而右大括号需要考虑缩进问题
        也就是说，先输出左大括号，再增加缩进。等输出完所有键值对后，先减少缩进，再输出右括号
        管辖范围：“{”到与之匹配的“}”
    */
    string formatJSON() {
        string formatted = "{\n";
        nowTo++;
        nowIndent += onceIndent;

        formatted += formatKeyValPair();

        nowIndent -= onceIndent;
        formatted += nSpaces(nowIndent);
        formatted += "}";
        nowTo++;  // }
        return formatted;
    }

    /*
        格式化键值对
    */
    string formatKeyValPair() {
        string formatted;
        while (s[nowTo] != '}') {
            formatted += nSpaces(nowIndent);
            formatted += '"';
            nowTo++;
            // 寻找 “":”
            while (s[nowTo] != '"') {
                formatted += s[nowTo++];
            }
            formatted += "\": ";
            nowTo += 2;  // "、:
            // 处理值
            if (s[nowTo] == '"') {  // 键值是字符串
                formatted += '"';
                nowTo++;
                while (s[nowTo] != '"') {
                    formatted += s[nowTo++];
                }
                formatted += '"';
                nowTo++;  // "
            }
            else {  // 键值是JSON对象
                formatted += formatJSON();
            }
            // 看是否有下一个键值对
            if (s[nowTo] == '}') {
                formatted += '\n';
            }
            else {
                formatted += ",\n";
                nowTo++;  // ,
            }
        }
        return formatted;
    }

    /*
        返回n个空格
    */
    string nSpaces(int n) {
        return string(n, ' ');
    }

public:
    JSONFormatter(string s) : s(s) {
        nowIndent = 0;
        onceIndent = 4;
        nowTo = 0;
    };

    string format() {
        return formatJSON();
    }
};

int main() {
    string s;
    cin >> s;
    JSONFormatter formatter(s);
    cout << formatter.format(); 
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101

    点关注，不迷路

    题解.md文件写了500多行呜呜呜

    原创不易，转载请附上原文链接哦~
    Tisfy：https://letmefly.blog.csdn.net/article/details/126473189

  • 相关阅读:
    移动端里调用高德APP并显示导航路线
    C嘎嘎 - 类和对象
    魔百盒M301H_JL代工_ADB可自由开关_强刷固件（可救砖）
    《微服务架构设计模式》第二章
    【文末福利】半导体封装率先国产化，400＋封装厂商最新名单汇总
    Solr安装使用教程
    Java.lang.Class类 getDeclaredMethod()方法有什么功能呢？
    区间DP 计数类DP 数位统计DP 状态压缩DP 树形DP 记忆化搜索
    单元测试中常见错误
    vue.js毕业设计，基于vue.js前后端分离在线教育视频点播系统（H5移动项目） 开题报告
  • 原文地址：https://blog.csdn.net/Tisfy/article/details/126473189