Decode String

Bài tập tham khảo tại leetcode Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Phân tích

1. Số chữ số trước [ có thể nhiều hơn 1. Do đó phải có hàm convert mảng chữ số sang số
2. Các khối [] có thể lồng nhau, phải xử lý nhân chuỗi trong khối [] sâu , sau đó lần ra khối [] ngoài. s = "3[a2[c]]"
3. Nếu có 2 khối [] đồng cấp, chúng ta xử lý tuần tự từ trái qua phải. s = "2[abc]3[cd]ef"

Xử lý khối [] lồng nhau sử dụng Stack

DD Biến:

• Stack, từng phần tử lưu chuỗi bên trong []
• Nếu chuỗi trong khối [] không còn chứa [] thì bắt đầu nhân chuỗi và pop
• Sau khi pop ra hết thì chạy tiếp.

Mỗi ngăn trong stack sẽ gồm:

• Hệ số nhân
• Vị trí ký tự [

Khi quét đến ký tự ] thì tính toán

x= hệ số nhân * chuỗi nằm giữa []

Quét đến ký tự ] thì tính

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

int convertToNumber(char *arrayNum);

char *decodeString(char *s);

char *multiplyString(char *s, int n);

int main() {
    char s1[] = "3[a]2[bc]";
    char s2[] = "3[a2[c]def]";  //nested []
    char s3[] = "2[abc]3[cd]ef";
    char *s = multiplyString("abcE", 5);
    printf("%s", s);
    free(s);
    return 0;
}

bool isNumberCharacter(char c) {
    if (c >= '0' && c <= '9') {
        return true;
    } else {
        return false;
    }
}

int convertToNumber(char *arrayNum) {
    int powerTen = 1;
    int result = 0;
    int len = strlen(arrayNum);
    for (int k = 0; k < len; k++) {
        result += powerTen * (arrayNum[len - 1 - k] - '0');
        powerTen *= 10;
    }

    return result;
}

char *multiplyString(char *s, int n) {
    int len = strlen(s);
    char *result = malloc(len * n * sizeof(char));

    for (int i = 0; i < n; i++) {
        strcpy(&result[i * len], s);
    }
    return result;
}

/* Ví dụ 3[a2[c]def]"
 * Khởi tạo empty stack
 * Khởi tạo biến stackHeight đến số lượng các khối [] lồng nhau ứng với một ký tự hiện thời
 * Chạy vòng lặp từ ký tự đầu đến cuối.
 *
 * Kiểm tra nếu ký t là chữ số 0-9 thì vào append vào một arrayNum
 * Nếu gặp ký tự '[' thì dừng, chuyển arrayNum sang số,
 * cho toàn bộ ký tự nằm giữa '[' và ']'
 * Nếu là ký tự thường:
 *    stackHeight == 0, thì append luôn chuỗi kết quả
 *    stackHeight > 0,
 *
 *
 *
 */
char *decodeString(char *s) {
    char *result = (char *) malloc(200 * sizeof(char));
    memset(result, 0, 200);

    char *stack = (char *) malloc(50 * sizeof(char));
    memset(stack, 0, 50);

    int stackHeight = 0;
    char numStr[5] = "";


    for (int i = 0; i < strlen(s); i++) {


        if (isNumberCharacter(s[i])) { //number
            strcat()
        } else if (s[i] == '[') { //open
            stackHeight++;
            //convert arrayNumbernumStr to number

        } else if (s[i] == ']') { //close
            //
        } else {  //Normal char

        }
    }


    free(stack);
    return result;
}