【LintCode】Expression Expand

題目描述

Given an expression s includes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.

測試資料

s = abc3[a] return abcaaa
s = [abc] return abcabcabc
s = [ac]dy, return acacacacdy
s = [[ad][pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz
           

解題思路

很明顯運算過程中具有嵌套的性質，需要使用棧來解決，又因為問題可分解，即将一個大的字元串看做

S = C + (N[S])* + C

，其中C表示常量字元串，即在本層次不需要擴充的字元串，N表示數字，S表示待處理的字元串，*表示後面的部分可以多次出現。這樣我們就可以通過遞歸來解決。

在使用遞歸的時候，對于C部分，直接加到結果中就行，問題在于中間的部分，即N[S]可能會出現多次，是以需要使用一個大循環，在循環中再遞歸。

另外，由于使用C語言實作，而C中并沒有字元串這種資料類型，在傳回結果的時候如果傳回指針也不可以，因為函數傳回的時候auto變量會被釋放，是以需要自己定義一個字元串類型用于傳回。

最後一個問題是對于原始字元串的周遊，需要在多層次的遞歸函數中保持指針位置的統一，是以使用了二重指針，這樣就可以讓不同層次的函數使用同一個指針進行操作。

C實作代碼

#include <stdio.h>

typedef struct string
{
    char data[];
    int length;
} string;

string expression_expand(char **src)
{
    int num = ;
    string single, repeat;//single表示未重複的字元串，repeat表示已經重複處理的字元串
    single.length = ;
    repeat.length = ;

    while(**src != '\0')
    {
        //首先将字元串中無需重複的部分取出
        while(**src >= 'a' && **src <= 'z' && **src != '\0')
        {
            repeat.data[repeat.length++] = **src;
            (*src)++;
        }
        //如果是數字，将數字提取出來
        while(**src >= '0' && **src <= '9' && **src != '\0')
        {
            num *= ;
            num += **src - '0';
            (*src)++;
        }
        //如果遇到'['，把後面字元串的重複工作交給下次遞歸處理
        if(**src == '[')
        {
            (*src)++;
            single = expression_expand(src);
        }
        //當獲得數字後面的字元串的處理結果之後，
        //由本次遞歸對整個結果進行重複處理
        while(num != )
        {
            num--;
            int i;
            for(i = ; i < single.length; i++)
            {
                repeat.data[repeat.length++] = single.data[i];
            }
        }
        //如果遇到']'，說明待重複的字元串已經提取完畢，傳回給上層遞歸
        if(**src == ']')
        {
            (*src)++;
            return repeat;
        }

    }
    return repeat;
}


int main(int argc, char *argv[])
{
    char data[];
    char *point;
    while(~scanf("%s", data))
    {
        point = data;
        string ret = expression_expand(&point);
        ret.data[ret.length] = '\0';
        printf("%s\n", ret.data);
    }
    return ;
}