I have expanded the data structure of 'NestedInteger'(like python list) and realized it.


  • 0
    E

    I have defined a data structure of 'nested_list'(expanded from 'NestedInteger' and just like python list, which can includes 'int','float','string' and the list of'int','float','string' ,i.e. it's a nested list.)

    //filename:nested_list.h
    //I have omitted some 'includes'
    //nested_list can include 'int','float','string' and the list of'int','float','string' ,i.e. it's a nested list.
    class nested_list{
     public:
      nested_list(const string&in);//string 'in' is the expression of nested_list with { and }, like "{1.23,{2,abc},{4.3},5,{efd,{7.01}}}"
      friend ostream& operator<<(ostream&os,nested_list&obj); //use "cout<<nested_list obj" to print the nested_list.
     private:
      int ele_int=0;
      float ele_float=0;
      string ele_str="";
      vector<nested_list> ele_list;
      int which_ele=0;//0:ele_int 1:ele_float 2:ele_str 3:ele_list
      static unordered_map<int,vector<int> >bracket_pair_hash;//key is the index+1 of the '{' in 'string in', value is a list storing the position of ',' and the pair '}'(in the end) of this sub-nested_list
      nested_list(const string&in,int st,int en,int type);//type:0:int/str 1:float 2:list
      void create_nested_list(const string&in,int st,int en,int type);//type:0:int/str 1:float 2:list 
    };
    
    //filename:nested_list.cpp
    unordered_map<int,vector<int> > nested_list::bracket_pair_hash;
    nested_list::nested_list(const string&in){
    //test the position of '{', '}', '.' and ','  with O(n)
     assert(in[0]=='{'); 
     int c=0;
     stack<int>s;
     for(int i=0;i<in.size();i++){
      if(in[i]=='{'){c++;s.push(i+1);bracket_pair_hash[i+1]=vector<int>{i+1};}
      else if(in[i]=='.')bracket_pair_hash[s.top()].back()*=-1;//means this sub-nested_list is a float
      else if(in[i]==',')bracket_pair_hash[s.top()].push_back(i+1);
      else if(in[i]=='}'){c--;assert(c>=0);bracket_pair_hash[s.top()].push_back(i+1);s.pop();}
     }
     assert(c==0);
     create_nested_list(in,0,in.size()-1,2);//O(m) m is number of elements in 'string in'
     bracket_pair_hash.clear();//for another nested_list 'string in'
    }
    nested_list::nested_list(const string&in,int st,int en,int type){//type:0:int/str 1:float 2:list
     create_nested_list(in,st,en,type);
    }
    void nested_list::create_nested_list(const string&in,int st,int en,int type){//type:0:int/str 1:float 2:list
     if(type==2){
      which_ele=3;
      for(int i=0;i<bracket_pair_hash[st+1].size()-1;i++){
       int pre=bracket_pair_hash[st+1][i],next=bracket_pair_hash[st+1][i+1];
       if(pre<0)ele_list.push_back(nested_list(in,abs(pre),abs(next)-2,1));
       else if(in[pre]=='{')ele_list.push_back(nested_list(in,pre,abs(next)-2,2));
       else ele_list.push_back(nested_list(in,pre,abs(next)-2,0));
      }
     }else if(type==1){
      which_ele=1;
      string::size_type sz;
      ele_float=stof(in.substr(st,en-st+1),&sz);
     }else if(isalpha(in[st])){
      which_ele=2;
      ele_str=in.substr(st,en-st+1);
     }else ele_int=stoi(in.substr(st,en-st+1));
    }
    ostream& operator<<(ostream&os,nested_list&obj){
     if(obj.which_ele==3){
      cout<<'{';
      for(int i=0;i<obj.ele_list.size();i++){
       os<<obj.ele_list[i];if(i<obj.ele_list.size()-1)cout<<",";
      }
      cout<<'}';
     }else if(obj.which_ele==0)cout<<obj.ele_int;
     else if(obj.which_ele==1)cout<<obj.ele_float;
     else cout<<obj.ele_str;
     return os;
    }
    
    //how to use this api
    #includes"./nested_list.h"
    string in="{1.23,{2,abc},{4.3},5,{efd,{7.01}}}";
    nested_list obj(in);
    cout<<obj<<endl; //print like "{1.23,{2,abc},{4.3},5,{efd,{7.01}}}";
    

    Tn=O(n+m) n is the length of "string in", m is the number of elements in "string in".


Log in to reply
 

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