华为机试（压缩算法）

为了提升数据传输的效率，会对传输的报文进行压缩处理。输入一个压缩后的报文，请返回它解压后的原始报文。压缩规则：

n[str]，表示方括号内部的str正好重复n次。注意n为正整数（0 < n <= 100），str只包含小写字母，不考虑异常情况。

输入描述：

输入压缩后的报文：

不考虑无效的输入，报文没有额外的空格，方括号总是符合格式要求的。

原始报文不包含数字，所有的数字只表示重复的次数n，例如不会出现像5b或者3[8]这种输入。

输出描述：

解压后的原始报文

示例1：

输入

3[k]2[mn]

输出

kkkmnmn

示例2：

输入

3[m2[c]]

输出

mccmccmcc

//压缩算法

#include <stdio.h>

#include<math.h>

#include<malloc.h>

#include<stdlib.h>

#include <string.h>

typedef struct stack

{

int Max = 100;

char*A = (char*)malloc(sizeof(char)* Max);

int top = -1;

};

void push(stack *stack, char c)

{

if (stack->top == stack->Max - 1)

return;

strcpy(&(stack->A[++stack->top]), &c);

}

char pop(stack *stack)

{

if (stack->top >= 0)

{

char topvalue=stack->A[stack->top];

stack->A[stack->top] = '\0';

stack->top--;

return topvalue;

}

return NULL;

}

char top(stack* stack)

{

if (stack->top >= 0)

return stack->A[stack->top];

return NULL;

}

int charToInt(char c)

{

if (c == '0')

return 0;

if (c == '1')

return 1;

if (c == '2')

return 2;

if (c == '3')

return 3;

if (c == '4')

return 4;

if (c == '5')

return 5;

if (c == '6')

return 6;

if (c == '7')

return 7;

if (c == '8')

return 8;

if (c == '9')

return 9;

return -1;

}

char*calculate(stack *stackInt, stack *stackChar)

{

//将stackInt里的char->int 用sun保存

int circle = stackInt->top + 1;

double sun = 0;

for (int i = 0; i < circle; i++)

{

sun += charToInt(pop(stackInt))* pow(10.0, i);

}

int countChar = stackChar->top + 1;

char* strChar = (char*)malloc(sizeof(char)*(countChar + 1));

memset(strChar, '\0', countChar + 1);

int i = 0;

while (NULL != top(stackChar))

{

strChar[i] = pop(stackChar);

i++;

}

char* str = (char*)malloc(sizeof(char)*(countChar*sun + 1));

memset(str, '\0', countChar*sun + 1);

for (int i = 0; i < sun; i++)

{

strcat(str, strChar);

}

return str;

}

int main()

{

char S[] = { '3', '[', 'M', '2', '[', 'C', ']', ']' };

stack stackChar;

stack stackInt;

stack stackStr;

memset(stackChar.A, '\0', stackChar.Max);

memset(stackInt.A, '\0', stackInt.Max);

memset(stackStr.A, '\0', stackStr.Max);

for (int i = 0; i < sizeof(S)/sizeof(S[0]); i++)

{

if (S[i] != ']')

{

push(&stackStr, S[i]);

}

else

{

while (top(&stackStr) != NULL&&top(&stackStr) != '[')

{

push(&stackChar, pop(&stackStr));

}

//skip [

pop(&stackStr);

while ('0'<=top(&stackStr) && top(&stackStr)<='9')

{

push(&stackInt, pop(&stackStr));

}

char* temp=calculate(&stackInt, &stackChar);

for (int i = 0; i < strlen(temp); i++)

{

push(&stackStr, temp[i]);

}

}

}

return 0;

}