Python & C++ solutions


  • 25

    Python using eval:

    def deserialize(self, s):
        def nestedInteger(x):
            if isinstance(x, int):
                return NestedInteger(x)
            lst = NestedInteger()
            for y in x:
                lst.add(nestedInteger(y))
            return lst
        return nestedInteger(eval(s))
    

    Python one-liner

    def deserialize(self, s):
        return NestedInteger(s) if isinstance(s, int) else reduce(lambda a, x: a.add(self.deserialize(x)) or a, s, NestedInteger()) if isinstance(s, list) else self.deserialize(eval(s))
    

    Python Golf (136 bytes or 31 bytes)

    class Solution:deserialize=d=lambda S,s,N=NestedInteger:s<[]and N(s)or s<''and reduce(lambda a,x:a.add(S.d(x))or a,s,N())or S.d(eval(s))
    

    Or abusing how the judge judges (yes, this gets accepted):

    class Solution:deserialize=eval
    

    Python parsing char by char

    Here I turned the input string into a list with sentinel for convenience.

    def deserialize(self, s):
        def nestedInteger():
            num = ''
            while s[-1] in '1234567890-':
                num += s.pop()
            if num:
                return NestedInteger(int(num))
            s.pop()
            lst = NestedInteger()
            while s[-1] != ']':
                lst.add(nestedInteger())
                if s[-1] == ',':
                    s.pop()
            s.pop()
            return lst
        s = list(' ' + s[::-1])
        return nestedInteger()
    

    C++ using istringstream

    class Solution {
    public:
        NestedInteger deserialize(string s) {
            istringstream in(s);
            return deserialize(in);
        }
    private:
        NestedInteger deserialize(istringstream &in) {
            int number;
            if (in >> number)
                return NestedInteger(number);
            in.clear();
            in.get();
            NestedInteger list;
            while (in.peek() != ']') {
                list.add(deserialize(in));
                if (in.peek() == ',')
                    in.get();
            }
            in.get();
            return list;
        }
    };
    

  • 3

    @StefanPochmann
    Hi, Stefan. There are some naming mistakes in your C++ solution, should look like this:

    class Solution {
    public:
        NestedInteger deserialize(string s) {
            istringstream in(s);
            return deserialize1(in);
        }
        
    private:
        NestedInteger deserialize1(istringstream &in) {
            int number;
            if (in >> number)
                return NestedInteger(number);
            in.clear();
            in.get();
            NestedInteger list;
            while (in.peek() != ']') {
                list.add(deserialize1(in));
                if (in.peek() == ',')
                    in.get();
            }
            in.get();
            return list;
        }
    };
    

  • 0

    @haruhiku Oops, thanks. I fixed it now. I had tried some alternatives and messed up extracting one for posting. I did mean to call the helper deserialize, btw, without the 1.


  • 0
    L

    @StefanPochmann
    Hi, Stefan. The C++ recursive solution is awesome .
    I can understand it, but i may not get the point where the recursion should begin. How you thinking the recursive solution?
    Do a mount of training ?hhahah, you do not need to reply.


  • 0
    L

    @StefanPochmann
    Hi, Stefan. I reproduce your c++ code and write my solution.
    0_1471316984435_upload-ad703d3c-a67d-49a8-b2ef-170cda2246d9

    unfortunately, in doesn't work.

    Any tips will be appreciated.

    =_=! I upload the picture cuz i don't know how to append the code .


  • 0
    L

    Hahahah, I fixed it. It works well.

    class Solution {
    public:
        NestedInteger deserialize(string s) {
            int i = 0;
            if (isdigit(s[i]) || s[i] == '-')
                return NestedInteger(stoi(s));
            ++i;
            NestedInteger list;
            while (s[i] != ']') {
                list.add(deserialize(s.substr(i, s.size() - i)));
                if(isdigit(s[i]) || s[i] == '-') {
                    while(isdigit(s[i]) || s[i] == '-')
                        ++i;
                }else {
                    i += num.top();
                    num.pop();
                }
                
                if (s[i] == ',')
                    ++i;
            }
            ++i;
            num.push(i);
            return list;
        }
    private:
        stack<int> num;
    };
    

    oh. the "stack<int> num" can be replaced by "int num",
    then "num.push(i)" ==> "num = i"
    " i += num.top();
    num.pop();" ==> "i += num"


  • 0
    P

    Can somebody explain why following line works?

     class Solution:deserialize=eval

  • 0
    C

    @haruhiku said in Python & C++ solutions:

    in.clear();
    in.get();

    Could u tell me what is the code mean? I want to solve the problem in C using your thinking,thanks,.


  • 2

    @Cot Actually I just correct the mistake in Stefan's code. For clear(), if I do not misunderstand, it's used for clearing the state of istringstream, you can look at this link:
    http://stackoverflow.com/questions/2848087/how-to-clear-stringstream
    But I think this will not have any effect on C because istringstream is mainly used in C++. The get() function is just used for getting the character in the stream and move to the next one.


  • 0
    C

    @haruhiku Thanks a lot,I will try my best to make it out.


  • 0

    I am parsing it char by char, and I get:

    0_1513957907289_57650b9f-f185-4db0-9a7f-71cb697e4ca3-image.png

    The nature of this problem makes it impossible to debug something like this. My code is the following

            def find(i):
                if s[i] != '[':
                    start = i
                    while s[i] in '-0123456789':
                        i += 1
                    if i > start:
                        stack[-1].add( NestedInteger(int(s[start:i])) )
                    
                    while s[i] == ']' and i < L:
                        stack[-2].add(stack.pop())
                        i += 1
                    
                    if s[i] == ',':
                        find(i+1)
                else:
                    stack.append(NestedInteger())
                    find(i+1)
                    
            if s[0] in '-0123456789':
                return NestedInteger( int(s) )
            
            stack = [NestedInteger()]
            L = len(s) - 1
            find(1)
            return stack[0]
    

    I appreciate it if anyone can help out


  • 0
    K

    Since s is a string, if we are allowed to use eval - I suppose this would be sufficient:

    def deserialize(self, s):
            """
            :type s: str
            :rtype: NestedInteger
            """
            return eval(s)
    

  • 0

    @kartikkannapur Yeah but... (1) I already posted that, actually a shorter version, in my Python Golf section and (2) that only works because the judge doesn't do its job well. Note you're supposed to return a NestedInteger, it's even in the docstring in your code. You instead return an int or list.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.