华为机试(压缩算法)
为了提升数据传输的效率,会对传输的报文进行压缩处理。输入一个压缩后的报文,请返回它解压后的原始报文。压缩规则:
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;
}