C++ recursive solution inspired by Kernighan's article "A regular expression Matcher"


  • 0
    G
    class Solution {
    public:
    
        string ParseStr(const string &s, int &Loc)
        {
            string Res;
            
            while(isalpha(s[Loc]))
            {
                Res.push_back(s[Loc++]);
            }
            
            return (Res);
        }
    
        string ParseBracket(const string &s, int &Loc)
        {
            
           string Res;
           
           if(isalpha(s[Loc]))
           {
               Res += ParseStr(s,Loc);
           }
           
           Res += decodeString(s,Loc);
           
           return (Res);
        }
    
        string ParseNumber(const string &s, int &Loc)
        {
            string Res;
            
            if(Loc == s.size())
            {
                return Res;
            }
            
            int Num =0 ;
            
            while(isdigit(s[Loc]))
            {
                Num = Num*10 + s[Loc] - '0';
                Loc++;
            }
            
            Loc++;
            
            string 
            Return = ParseBracket(s,Loc);
            
            for(int i = 0; i < Num; ++i)
            {
                Res += Return;
            }
            
            return (Res);
        }
        
        string decodeString(const string &s, int &Loc)
        {
            string Res;
            
            if(Loc == s.size())
            {
                return Res;
            }
            
            if(isdigit(s[Loc]))
            {
                Res += ParseNumber(s,Loc);
            }
            else if(isalpha(s[Loc]))
            {
                Res += ParseStr(s,Loc);
            }
            else // this is the case we encounter closing square bracket
            {
                Loc++;
                return Res;
            }
            
            Res += 
            decodeString(s,Loc);
            
            return (Res);
        }
        
        string decodeString(string s) 
        {
            int Loc = 0;
            return decodeString(s,Loc);
        }
    };

Log in to reply
 

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