Decode String - C Solution

1. Introduction

This blog post explores a fascinating problem in string manipulation using C programming: decoding a string that follows a specific encoding rule. This challenge is an excellent exercise in understanding stacks and string operations, commonly used in parsing and interpreting data.

Problem

Given an encoded string, the task is to return its decoded string. The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. The challenge is to correctly interpret and expand these encoded patterns.

2. Solution Steps

1. Use a stack to store characters of the encoded string.

2. Iterate through each character of the string.

3. When a number is encountered, convert it to an integer.

4. When an opening bracket is encountered, push the number and reset it.

5. On encountering a closing bracket, pop and repeat the string inside the brackets.

6. Construct the decoded string from the stack.

3. Code Program

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

#define MAX_LEN 105 // Maximum length of the output

// Stack structure definition
typedef struct {
    char data[MAX_LEN];
    int top;
} Stack;

// Function to initialize the stack
void stackInit(Stack *s) {
    s->top = -1;
}

// Function to push an element onto the stack
void stackPush(Stack *s, char element) {
    s->data[++(s->top)] = element;
}

// Function to pop an element from the stack
char stackPop(Stack *s) {
    return s->data[(s->top)--];
}

// Function to check if the stack is empty
int stackIsEmpty(Stack *s) {
    return s->top == -1;
}

// Function to decode the string
char* decodeString(char *s) {
    Stack stack;
    stackInit(&stack);
    int num = 0;

    for (int i = 0; s[i] != '\0'; i++) {
        if (isdigit(s[i])) {
            num = num * 10 + (s[i] - '0');
        } else if (s[i] == '[') {
            stackPush(&stack, num);
            num = 0;
        } else if (s[i] == ']') {
            // Pop string and repeat it
            char temp[MAX_LEN], result[MAX_LEN] = "";
            int count = stackPop(&stack);
            while (!stackIsEmpty(&stack) && !isdigit(stack.data[stack.top])) {
                temp[strlen(temp) + 1] = '\0';
                temp[strlen(temp)] = stackPop(&stack);
            }
            for (int j = 0; j < count; j++) {
                strcat(result, temp);
            }
            // Push result back to stack
            for (int j = 0; result[j] != '\0'; j++) {
                stackPush(&stack, result[j]);
            }
        } else {
            stackPush(&stack, s[i]);
        }
    }

    char *decoded = (char *)malloc(MAX_LEN * sizeof(char));
    for (int i = stack.top; i >= 0; i--) {
        decoded[stack.top - i] = stack.data[i];
    }
    decoded[stack.top + 1] = '\0';
    return decoded;
}

// Main function to demonstrate decodeString function
int main() {
    char s[] = "3[a]2[bc]"; // Example input
    char *decoded = decodeString(s); // Call the decode function
    printf("Output: %s\n", decoded); // Print the result
    free(decoded); // Free the allocated memory
    return 0;
}

Output:

aaabcbc

Explanation:

The program decodes the string "3[a]2[bc]" by using a stack to manage the encoding logic. It processes each character of the string, converting numbers to integers and handling brackets to expand the encoded patterns. 

When a closing bracket is encountered, the string within the brackets is popped, repeated as per the preceding number, and the result is pushed back onto the stack. 

Finally, the stack contents are used to construct the decoded string, resulting in "aaabcbc". 

This method effectively decodes the string using a stack-based approach to handle the nested encoded patterns.