394. 字符串解码

题目链接：https://leetcode-cn.com/problems/decode-string/

解题思路

看到括号相关的题目，瞬间就想到了利用栈的特性，细读题意发现这道题的确很适合用栈来做。
首先在碰到 ']' 字符之前不断的将字符串入栈，当碰到 ']' 字符之后，不断的将栈中元素出栈，出栈的时候要注意判断是否是数字，在碰到数字之前的元素都为字母，将其赋值给s1，碰到数字字符之后将其赋值给s2，直到再碰到非数字字符。
而后分别逆转s1和s2，同时将逆转之后的s2通过atoi()函数转为int类型的i来标记字符串重复次数。
将逆转之后的s1重复i次，再推入原先的栈中，而后继续将原先的字符串入栈。
最后字符串全部入栈之后，依次取出，再次逆转就得到了最终的结果。

代码(略丑，轻喷)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STACK_MAX_LENGTH 10001

struct char_stack {
    char s[STACK_MAX_LENGTH];
    int depth;
};

void reverse_str(char *str) {
    for (size_t i = 0, j = strlen(str) - 1; i < j; ++i, --j) {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }
}

void generate_str(struct char_stack* ch_stack) {
    char *str = (char *)malloc(sizeof(char) * STACK_MAX_LENGTH);
    memset(str, '\0', sizeof(char) * STACK_MAX_LENGTH);
    int str_count = 0;
    char *in = (char *)malloc(sizeof(char) * STACK_MAX_LENGTH);
    memset(in, '\0', sizeof(char) * STACK_MAX_LENGTH);
    int in_count = 0;
    while (!(ch_stack->s[ch_stack->depth - 1] >= '0'
             && ch_stack->s[ch_stack->depth - 1] <= '9')) {
        str[str_count++] = ch_stack->s[--ch_stack->depth];
        if (ch_stack->s[ch_stack->depth - 1] == '[') {
            --ch_stack->depth;
            break;
        }
    }

    while (ch_stack->depth > 0
           &&ch_stack->s[ch_stack->depth - 1] >= '0'
           && ch_stack->s[ch_stack->depth - 1] <= '9') {
        in[in_count++] = ch_stack->s[--ch_stack->depth];
    }

    reverse_str(str);
    reverse_str(in);

    int repeat_time = atoi(in);

    while (repeat_time--) {
        for (size_t i = 0; i < strlen(str); ++i) {
            ch_stack->s[ch_stack->depth++] = str[i];
        }
    }
}

char * decodeString(char * s) {
    if (s == NULL) {
        return NULL;
    }
    if (strlen(s) == 0) {
        return "";
    }
    struct char_stack ch_stack;
    memset(ch_stack.s, '\0', sizeof(char) * STACK_MAX_LENGTH);
    ch_stack.depth = 0;
    for (size_t i = 0; i < strlen(s); ++i) {
        if (s[i] == '[') {
            ch_stack.s[ch_stack.depth++] = '[';
        } else if ((s[i] >= '0' && s[i] <= '9')
        || (s[i] >= 'a' && s[i] <= 'z')
        || (s[i] >= 'A' && s[i] <= 'Z')) {
            ch_stack.s[ch_stack.depth++] = s[i];
        } else if (s[i] == ']') {
            generate_str(&ch_stack);
        }
    }
    char *result = (char *)malloc(sizeof(char) * STACK_MAX_LENGTH);
    memset(result, '\0', sizeof(char) * STACK_MAX_LENGTH);
    int result_count = 0;
    while (ch_stack.depth) {
        result[result_count++] = ch_stack.s[--ch_stack.depth];
    }
    reverse_str(result);
    return result;
}

int main() {
    char *s = (char *)malloc(sizeof(char) * STACK_MAX_LENGTH);
    memset(s, '\0', sizeof(char) * STACK_MAX_LENGTH);
    scanf("%s", s);
    char *result = decodeString(s);
    printf("%s", result);
    return 0;
}