385.迷你语法分析器

链接：385.迷你语法分析器
难度：Medium
标签：栈、深度优先搜索、字符串
简介：给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。

题解 1 - cpp

• 编辑时间：2022-03-19
• 执行用时：12ms
• 内存消耗：12.9MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
   public:
    NestedInteger deserialize(string s) {
        if (s[0] == '[') return analysis(s.substr(1, s.size() - 2));
        NestedInteger ans;
        ans.setInteger(stoi(s));
        return ans;
    }
    NestedInteger analysis(const string &s) {
        NestedInteger ans;
        vector<int> res = find_split(s);
        int prev = -1;
        for (auto &split : res) {
            ans.add(deserialize(s.substr(prev + 1, split - prev - 1)));
            prev = split;
        }
        string last = s.substr(prev + 1, s.size() - prev - 1);
        if (last != "") ans.add(deserialize(last));
        return ans;
    }
    vector<int> find_split(const string &s) {
        int deep = 0;
        vector<int> ans;
        for (int i = 0; i < s.size(); i++) {
            if (deep == 0 && s[i] == ',')
                ans.push_back(i);
            else if (s[i] == '[')
                deep++;
            else if (s[i] == ']')
                deep--;
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-04-15
• 执行用时：8ms
• 内存消耗：12.3MB
• 编程语言：cpp
• 解法介绍：递归遍历。

class Solution {
   public:
    NestedInteger deserialize(string s) {
        NestedInteger res;
        if (s == "[]")
            return res;
        else if (s[0] == '[')
            split(res, s.substr(1, s.size() - 2));
        else
            res.setInteger(stoi(s));
        return res;
    }
    void split(NestedInteger &obj, string s) {
        int level = 0, start = 0, n = s.size();
        for (int i = 0; i < n; i++) {
            char ch = s[i];
            if (ch == '[')
                level++;
            else if (ch == ']')
                level--;
            else if (ch == ',' && level == 0)
                obj.add(deserialize(s.substr(start, i - start))), start = i + 1;
        }
        obj.add(deserialize(s.substr(start, n - start)));
    }
};