Leetcode 385. Mini Parser

ゝ一纸荒年。 2022-07-17 04:39 101阅读 0赞

**题意**  
这题看题看了好久，不太理解题意。觉得Leetcode的难度在于理解题目上面。

题意是根据所给的字符串，解析出一个NestedInteger的对象。  
解析的方式就是最简单的自动机。  
因为很类似递归处理，所以用一个栈来维护每一层的NestedInteger。

然后返回最顶层的就行了。

(Leetcode代码收录\]([https://github.com/Mr-Phoebe/ACM-ICPC/tree/master/OJ/Leetcode][https_github.com_Mr-Phoebe_ACM-ICPC_tree_master_OJ_Leetcode])，求粉求星星。

/**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * class NestedInteger { 
     *   public:
     *     // Constructor initializes an empty nested list.
     *     NestedInteger();
     *
     *     // Constructor initializes a single integer.
     *     NestedInteger(int value);
     *
     *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
     *     bool isInteger() const;
     *
     *     // Return the single integer that this NestedInteger holds, if it holds a single integer
     *     // The result is undefined if this NestedInteger holds a nested list
     *     int getInteger() const;
     *
     *     // Set this NestedInteger to hold a single integer.
     *     void setInteger(int value);
     *
     *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
     *     void add(const NestedInteger &ni);
     *
     *     // Return the nested list that this NestedInteger holds, if it holds a nested list
     *     // The result is undefined if this NestedInteger holds a single integer
     *     const vector<NestedInteger> &getList() const;
     * };
     */
    class Solution { 
    public:  
        NestedInteger deserialize(string s) {  
            if(s[0] != '[') return NestedInteger(stoi(s));  
            stack<NestedInteger*> stk;  
            NestedInteger* ans = NULL;  
            int idx = 0;  
    
            for(int i=0; i<s.size(); i++) {  
                if(s[i] == '[') {  
                    stk.push(new NestedInteger());  
                    if(!ans) ans = stk.top();  
                    idx = i + 1;  
                }  
                else if(s[i] == ',') {
                    if(idx != i)  
                        stk.top()->add(NestedInteger(stoi(s.substr(idx, i-idx))));  
                    idx = i + 1;
                }
                else if(s[i] == ']') {  
                    if(idx != i)  
                        stk.top()->add(NestedInteger(stoi(s.substr(idx, i-idx)))); 
                    NestedInteger* cur = stk.top();  
                    stk.pop();  
                    if(!stk.empty()) stk.top()->add(*cur);  
                    idx = i + 1;  
                }  
            }  
    
            return *ans;  
        }  
    };

[https_github.com_Mr-Phoebe_ACM-ICPC_tree_master_OJ_Leetcode]: https://github.com/Mr-Phoebe/ACM-ICPC/tree/master/OJ/Leetcode