Trivial solution with two stacks (Python code)


  • 0
    X

    The question resembles the implement of eval function to some degree. I try to avoid the use of some build-in functions to finish the general process.

    First of all, two stacks operator and operand are defined to store operators (e.g. '[',']'and',') and operands (e.g. NestedIntegers, but we need a variable temp to take the int value from digit to digit then construct into NestedInteger obejects) respectively. Then, we can take the chars in the string successively to do the following operation:

    • '[' means the beginning of a NestedInteger Object, so just push it into the operator. If there is a non-empty string in temp, make a NestedInteger with the value, push the NestedInteger into operand, and then reset temp.

    • ',' also implies the beginning of a new NestedInteger different from the previous one. Therefore, just treat it as '[' when you visit the string.

    • ']' means the end of a NestedInteger, so when you come across it: firstly treat non-empty temp as cases before, make it a NestedInteger pushed into operand. Then you should continously pop one element from two stacks simultaneously until a '[' popped from operator. Merge all those NestedIntegers popped from operand into a NestedInteger using add method ( this is what the operator ',' exactly means), and push the new NestedInteger into operand

    • [0-9],- just take the place of one digit or sign in a int value, so keep it simply with temp += s[i].

    My code:

    class Solution(object):
        def deserialize(self, s):
            temp=""
            operator=[]
            operand=[]
            for i in range(len(s)):
                if s[i]=='[' or s[i]==',':
                    operator.append(s[i])
                    if temp!="":
                        operand.append(NestedInteger(int(temp)))
                        temp=""
                elif s[i]==']':
                    if temp == "" and s[i-1] == '[':
                        operand.append(NestedInteger())
                        operator.pop()
                    else:
                        if temp != "":
                            operand.append(NestedInteger(int(temp)))
                            temp = ""
                        temp_sum=NestedInteger()
                        temp_list=[operand.pop()]
                        op=operator.pop()
                        while op !='[':
                            temp_list.append(operand.pop())
                            op=operator.pop()
                        while temp_list:
                            temp_sum.add(temp_list.pop())
                        operand.append(temp_sum)
                else:
                    start=True
                    temp=temp+s[i]
            if temp!="":
                return NestedInteger(int(temp))
            else:
                return operand[0]
    

    Besides, you'd better pay more attention to the case of empty NestedInteger ( [] appear in string ) due to no restriction for the situation in the description. Some when you come across s[i]='[', first check if s[i-1]=']'.


Log in to reply
 

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