71. Simplify Path

// 演算法 / Algorithm:
// 用 '/' 切割路徑，逐段處理；空字串與 "." 跳過，".." 退回上一層，其餘 push。
// Split on '/'; skip "" and ".", pop on "..", push everything else.
// 我們用一個指標陣列 stack[] 記錄每段目錄在緩衝區中的位置與長度。
// We keep a stack of (start,length) for each kept directory, then join them.

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

char* simplifyPath(char* path) {
    int n = (int)strlen(path);              // 路徑長度 / length of the input path

    // 緩衝區：複製一份 path，方便我們就地切出每個片段
    // Buffer: a copy of path so we can carve tokens out of it.
    char* buf = (char*)malloc((size_t)n + 1); // +1 給結尾的 '' / room for the '' terminator
    strcpy(buf, path);                        // 把 path 的內容複製進 buf / copy contents in

    // stack 存「每個保留目錄的起始指標」，最多不會超過 n 段
    // stack holds a start-pointer for each kept directory; at most n of them.
    char** stack = (char**)malloc(sizeof(char*) * (size_t)n);
    int top = 0;                              // 堆疊大小 / number of items on the stack

    int i = 0;                                // 目前掃描位置 / current scan index
    while (i < n) {
        // 跳過分隔用的斜線；連續多個斜線會在這裡一起被略過
        // Skip slash separators; consecutive slashes are all skipped here.
        if (buf[i] == '/') { i++; continue; }

        // 找到一個片段的開頭，記住起點 / found a token start, remember where it begins
        int start = i;
        while (i < n && buf[i] != '/') i++;   // 一直走到下一個 '/' 或字串結尾 / advance to next '/'
        buf[i] = '';                        // 把該 '/' 改成 ''，讓這段成為獨立 C 字串
                                              // turn the '/' into '' so the token is its own string
        char* tok = &buf[start];              // tok 指向這個片段 / tok points at the token
        i++;                                  // 跳過剛剛寫入的 ''（原本是 '/') / step past it

        if (strcmp(tok, ".") == 0) {
            // "." 代表目前目錄，忽略 / "." means current dir, ignore
            continue;
        } else if (strcmp(tok, "..") == 0) {
            // ".." 代表上一層；堆疊非空才 pop（根目錄無法再上去）
            // ".." means parent; pop only if non-empty (cannot go above root)
            if (top > 0) top--;
        } else {
            // 其他都是合法目錄名（含 "..."），push 進堆疊
            // anything else is a valid directory name (incl. "..."), push it
            stack[top++] = tok;
        }
    }

    // 組合答案：最長情況約等於原長度，配置 n+2 一定夠
    // Build the answer; n+2 bytes is always enough (leading '/' + '').
    char* res = (char*)malloc((size_t)n + 2);
    int len = 0;                              // 已寫入的字元數 / chars written so far

    if (top == 0) {
        // 堆疊為空 => 根目錄 / empty stack => root directory
        res[len++] = '/';
    } else {
        // 每個目錄前面加一個 '/' 再接目錄名 / prefix each dir with one '/'
        for (int k = 0; k < top; k++) {
            res[len++] = '/';                 // 分隔斜線 / the single separating slash
            int L = (int)strlen(stack[k]);    // 這段目錄名長度 / length of this dir name
            memcpy(&res[len], stack[k], (size_t)L); // 複製目錄名到結果 / copy the name in
            len += L;                         // 移動寫入位置 / advance write position
        }
    }
    res[len] = '';                          // 收尾，C 字串必須以 '' 結束 / null-terminate

    free(stack);                              // 釋放暫存堆疊 / free temporary stack
    free(buf);                                // 釋放路徑副本 / free the path copy
    return res;                               // 回傳結果（呼叫端負責 free）/ caller owns res
}

// 演算法 / Algorithm:
// 用 stringstream + getline 以 '/' 切片，逐段處理：
// "" 與 "." 跳過，".." 對 vector pop_back，其餘 push_back，最後接成 "/a/b/c"。
// Tokenize on '/', skip ""/".", pop on "..", push otherwise, then join.

#include <string>
#include <vector>
#include <sstream>

class Solution {
public:
    std::string simplifyPath(std::string path) {
        std::vector<std::string> stack;       // 當作堆疊用的動態陣列 / vector used as a stack
        std::stringstream ss(path);           // 把 path 包成可讀的串流 / wrap path as a stream
        std::string token;                    // 每次取出的片段 / one segment per read

        // getline 以 '/' 為分隔符，一次讀出兩個 '/' 之間的內容
        // getline with '/' delimiter yields the text between two slashes.
        // 連續斜線會產生空字串 token，下面會被跳過。
        // Consecutive slashes yield empty tokens, skipped below.
        while (std::getline(ss, token, '/')) {
            if (token.empty() || token == ".") {
                // 空片段（連續斜線）或 "."（目前目錄）都忽略
                // empty token (multiple slashes) or "." (current dir): ignore
                continue;
            } else if (token == "..") {
                // 回到上一層：非空才 pop / go up: pop only if non-empty
                if (!stack.empty()) stack.pop_back();
            } else {
                // 合法目錄名，push 到尾端 / valid name, push to the back
                stack.push_back(token);
            }
        }

        // 組合結果：根目錄時為 "/"，否則 "/" + 每段用 '/' 連接
        // Build result: "/" for root, else each dir prefixed by '/'.
        std::string result;
        if (stack.empty()) return "/";        // 堆疊空 => 根目錄 / empty => root

        for (const std::string& dir : stack) { // range-for 逐一走訪 / range-for over each dir
            result += '/';                    // 先放一個分隔斜線 / one separating slash
            result += dir;                    // 再接目錄名 / then the directory name
        }
        return result;                        // 例如 "/home/user/Pictures"
    }
};