LintCode-分治-Expression Expand

點此直接進入題目

解題思路：首先題目要求是給一個字元串，然後展開。展開是将[ ]内的字元串進行展開，而且展開的次數是，[ ]前的數字。大體思路有了以後進行細化。一個字元串它可以[ ]裡面包着很多[ ]，我們可以對最裡面的[ ]的字元串進行展開。例如：3[2[ad]3[pf]]xyz，先對最裡面的字元串進行展開，得到3[adadpfpfpf]xyz,然後在展開得到adadpfpfpfadadpfpfpfadadpfpfpfxyz。

解題過程：給定一個字元串s,定義一個字元串a，利用atoi判斷s的某個字元是否是數字。利用while語句，條件是s的長度不為0，然後從s第一個字元開始判斷，若該字元不是數字，則将該字元加到a的末尾。否則，利用atoi将該字元或多個字元轉化成數字num，stringsteam将該數字轉化成字元串，求得該數字位數，然後從s的第一位字元期删除相應數量的字元，然後将[ ]内的字元指派給新的字元串aa,并且在s中删除相應字元串。aa内可能會有[],是以對aa進行遞歸。然後将aa遞歸結果指派給b，然後将b加到字元串a後面num次。最後傳回a.

代碼實作：string expressionExpand(string &s){

       string a;

   while(s.length())\\s長度不為0

    {

       int num=atoi(s.c_str());\\判斷s的第一位是不是數字。

       stringstream ss;

       ss<<num;

       string b=ss.str();\\求得數字長度

       if(num||(b.length()==1&&s[0]=='0'))\\s的前幾位是數字的情況

       {

            s.erase(0,1+b.length())\\删除s的前幾位數字以及數字後面的‘[‘符号。

           int count=1;

           string aa;

           while(1)

           {

                if(s[0]=='[')

                {

                    count++;

                }

                else if(s[0]==']')

                {

                    count--;

                }

                if(count==0) break;

                else{

                    aa+=s[0];

                    s.erase(0,1);

                }

            }\\将s的[ ]内字元串指派給aa

           b=expressionExpand(aa);\\aa進行遞歸，并将結果給b

           while(num)\\對b進行擴充

           {

                a+=b;

                num--;

           }

       }

       else{\\若s的首位不是數字的話，就直接将字元加到a後面，并且删除該字元

               if(s[0]!='['&&s[0]!=']') a+=s[0];

                s.erase(0,1);

        }

    }

   return a;

    }

注意事項：要注意字元串的用法，尤其是删除操作，string轉化int操作，而且思路要清晰。而且要注意字元串内0是字元，轉化後還是0，但是此時要對0後面括号内的字元展開0次，但是若該字元不是數字，轉化得到的也是0，但此時不對後面字元展開，而且該字元後面也沒有括号[]，這裡需要注意。

個人總結：我在字元串是0的那個地方栽了一次，沒想到那點上去。