LeetCode 385. Mini Parser

思路

一开始还以为又回到了编译原理，想到了状态转换图啊之类的。后来发现这个题目没有这么变态，要考虑的是个栈的问题。
为什么会想到栈呢？因为看到了括号，因为括号结束的时候我们要把某个部分的内容添到更大的括号里头去。
我的处理方式是：

• 构造一个工作栈，一开始是空的
•  碰到数字
  • 生成一个只包含数字的NestedInteger
    • 如果工作栈空，那么字符串就是个纯数字，直接返回
    • 如果工作栈非空，那么这个字符串就要加到当前工作栈顶端的元素后面（考虑情况[35,345]这种）
• 碰到'[‘
  • 新建一个空的NestedInteger（至于里面填什么，不是这里要考虑的事儿）
  • 把它压入栈
• 碰到’]’
  • 取出当前栈顶元素formerTop
  • 判断栈是否空了
    • 非空，则formerTop要加到当前栈顶的后面
    • 空，可以返回了
• 碰到’,’
  • 其实没什么用，往前挪动吧

这个步骤还能再精简一下的，判断栈是否空，是否返回的部分是重复了

代码

/**
 * // 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 {
private:
    stack<NestedInteger*> workingStack;
public:
    int readIntVal(const string& s, int& pos)
    {
        // pos will be set to the end index of current integer
        int value = 0;
        bool neg = false;
        if(s[pos] == '-'){
            neg = true;
            pos++;
        }
        while(pos < s.size() &&
                (s[pos] >= '0' && s[pos] <= '9'))
        {
            value *= 10;
            value += (s[pos] - '0');
            pos++;
        }
        pos--;
        return neg? -value : value;
    }
    NestedInteger deserialize(string s) {
        int pos = 0;
        while(pos < s.size())
        {
            char c = s[pos];
            if(c == '-' || (c >= '0' && c <= '9'))
            {
                NestedInteger* digitNI = new NestedInteger(readIntVal(s, pos)); //Integer containing NestedInteger
                if(workingStack.empty())
                {
                    //Should return
                    return *digitNI;
                }
                else
                {
                    //Append to existing NI
                    NestedInteger* currNI = workingStack.top();
                    currNI->add(*digitNI);
                    pos++;
                }
            }
            else if(c == ',')
            {
                pos++;
            }
            else if(c == '[')
            {
                //Create an NI and push to working stack
                NestedInteger* ni = new NestedInteger();
                workingStack.push(ni);
                pos++;
            }
            else if(c == ']')
            {
                //pop workingStack and append former-top item to current top
                NestedInteger* formerTop = workingStack.top();
                workingStack.pop();
                if(workingStack.empty())
                    return *formerTop;
                else
                {
                    //Append
                    NestedInteger* currTop = workingStack.top();
                    currTop->add(*formerTop);
                    pos++;
                }
            }
        }
        //Shouldn't be here!
        return NestedInteger();
    }
};

题目

Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list — whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:

• String is non-empty.
• String does not contain white spaces.
• String contains only digits 0-9, [, - ,, ].

Example 1:

Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.