# 0ms C example with recursive and link list

• I cannot find a C example in this discussion so I want to share my idea.
Basically I solve it by recursive function and self designed link list.

``````/*
* Node structure:
*    cnt               - The repeat count for current node.
*    len               - The string length in current node.
*                          (From pCurStr or the sum of all child node)
*    pCurStr       - The sub-string content. (note)
*    pChildNxt    - Link to child nodes.
*    pSubStrNxt - Link to next nodes.
* Note:
*    For a set of characters, it will create a node to save the content.
*    For a set of characters in "[]", it will create a child node.
*    Ex.
*        it contains:
*        node(efg)  -> child(repeat 13)
*                              => node(ad) -> child(repeat 23) -> node(abg)
*                                                       => node(tyu)
*
*/
struct StringNode {
int cnt;
int len;
char *pCurStr;
struct StringNode *pChildNxt;
struct StringNode *pSubStrNxt;
};
/*
* This func is to count the sub-string length.
* ex.
*      char *s = "ef2[abc]"
*      sub-string is "ef"
*      CntToSubStrEnd(s) will return 2
*/
int CntToSubStrEnd(char *s) {
int RetVal = 0;
while (*s && ((*s < '0') || (*s > '9')) && (*s != '[') && (*s != ']')) {
s++;
RetVal++;
}
return RetVal;
}
/*
* This func will parse the number
* ex.
*      char *s = "12[abc]"
*      GetNum(s, &Num) will return 2 and Num will equals to 12
*/
int GetNum(char *s, int *pNum) {
int RetVal = 0;
*pNum = 0;
while (*s && (*s >= '0') && (*s <= '9')) {
*pNum = *pNum * 10;
*pNum = *pNum + *s - '0';
RetVal++;
s++;
}
return RetVal;
}
/*
* This func will count the length between '[' and ']'
* ex.
*      char *s = "12[abc]"
*      CntSymboInterval(s) will return 3
*/
int CntSymboInterval(char *s) {
int Flag = 1;
int RetVal = 0;
//Move to first symbo
while (*s != '[') s++;
s++;
while (*s && Flag) {
if (*s == '[')
Flag++;
else if (*s == ']')
Flag--;
RetVal++;
s++;
}
RetVal--;
return RetVal;
}
/*
* Main recursive function to process string
*/
int StringProc(char *s, int len, struct StringNode **pNode) {
int i;
int CurStrLen = 0;
int AccumStrLen = 0;
int ProcLen = 0;
struct StringNode *pCurNode;
pCurNode = (struct StringNode *)calloc(1, sizeof(struct StringNode));
*pNode = pCurNode;
while (ProcLen < len) {
if ((*s >= '0') && (*s <= '9')) {
CurStrLen = GetNum(s, &(pCurNode->cnt));
s += CurStrLen;
ProcLen += CurStrLen;
CurStrLen = CntSymboInterval(s);
pCurNode->len = StringProc(s + 1
, CurStrLen
, &(pCurNode->pChildNxt));
s = s + 2 + CurStrLen;
AccumStrLen += ((pCurNode->len) * (pCurNode->cnt));
ProcLen += (CurStrLen + 2);
}
else {
CurStrLen = CntToSubStrEnd(s);
pCurNode->cnt = 1;
pCurNode->len = CurStrLen;
pCurNode->pCurStr = (char *)malloc((CurStrLen + 1) * sizeof(char));
for (i = 0; i < CurStrLen; i++) {
*(pCurNode->pCurStr + i) = *(s + i);
}
*(pCurNode->pCurStr + i) = 0;
s += CurStrLen;
AccumStrLen += CurStrLen;
ProcLen += CurStrLen;
}
if (ProcLen < len) {
pCurNode->pSubStrNxt
= (struct StringNode *)calloc(1, sizeof(struct StringNode));
pCurNode = pCurNode->pSubStrNxt;
}
}
return AccumStrLen;
}
/*
* Main recursive function to fill in output string
*/
void FillInStr(struct StringNode *pHead, char *pDst) {
int i, j;
struct StringNode *pSubN;
for (i = 0; i < pHead->cnt; i++) {
for (j = 0; j < pHead->len; j++) {
*(pDst + j) = *(pHead->pCurStr + j);
}
}
else {
FillInStr(pSubN, pDst);
}
}
}
}

char* decodeString(char* s) {
char *pRet;
int len = strlen(s);
if (len == 0) {
pRet = (char *)malloc(sizeof(char));
*pRet = 0;
return pRet;
}