Simplify Path - C Solution

1. Introduction

In this post, we tackle a common problem in file system path manipulation, known as "Simplify Path". This challenge is about converting an absolute path in a Unix-style file system into a simplified canonical path. It's a great example of string parsing and stack usage in C programming.

Problem

Given an absolute path path to a file or directory in a Unix-style file system, the task is to convert it into a simplified canonical path. The canonical path should start with a single slash '/', have directories separated by a single slash '/', not end with a trailing '/', and only contain the directories from the root to the target.

2. Solution Steps

1. Use a stack data structure to process the path components.

2. Split the path string by '/' and iterate through each component.

3. If a component is a period '.' or empty, ignore it.

4. If a component is a double period '..', pop the top element from the stack if it's not empty.

5. If a component is a directory name, push it onto the stack.

6. Construct the canonical path from the stack content.

7. Return the simplified path.

3. Code Program

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

// Function to simplify the path
char* simplifyPath(char* path) {
    char** stack = (char**)malloc(strlen(path) * sizeof(char*));
    int top = -1;

    char* token = strtok(path, "/");
    while (token != NULL) {
        if (strcmp(token, "..") == 0) {
            if (top > -1) top--; // Go up a directory (pop from stack)
        } else if (strcmp(token, ".") != 0 && strcmp(token, "") != 0) {
            stack[++top] = token; // Push directory to stack
        }
        token = strtok(NULL, "/");
    }

    char* result = (char*)malloc(strlen(path) + 1);
    strcpy(result, "/");
    for (int i = 0; i <= top; i++) {
        strcat(result, stack[i]);
        if (i < top) strcat(result, "/");
    }

    free(stack);
    return result;
}

// Main function to test the simplifyPath function
int main() {
    char path[] = "/a/./b/../../c/";
    char* simplifiedPath = simplifyPath(path);
    printf("Simplified Path: %s\n", simplifiedPath);
    free(simplifiedPath);

    return 0;
}

Output:

Simplified Path: /c

Explanation:

1. The path is split into components using '/' as a delimiter.

2. Components are processed and added to the stack based on Unix path rules.

3. The canonical path is reconstructed from the stack.

4. simplifyPath handles cases like '.', '..', and extra '/'.

5. The main function demonstrates the functionality with an example path.