LeetCode 簡化 Unix 路徑：棧處理相對路徑符號

題目描述

給定 Unix 風格絕對路徑，簡化為標準規範路徑：

• . 表示當前目錄
• .. 表示上級目錄（根目錄的上級仍是根目錄）
• 多個 / 視為單個分隔符

範例：

輸入: "/a/./b/../../c/"
輸出: "/c"

輸入: "/home/" → "/home"
輸入: "/../../" → "/"

解題思路：棧模擬目錄遍歷

1. 按 / 分割路徑字符串
2. 遍歷各段：

• 空串或 .：忽略
• ..：棧非空時彈出（回到上級）
• 其他：壓入棧（進入子目錄）

3. 棧底放入空串代表根目錄，最後 / 連接棧內元素

時間複雜度：O(n)，空間複雜度：O(n)。

Python 參考實現

class Solution:
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        parts = path.split('/')
        stack = ['']  # 棧底放空串代表根目錄 "/"
        
        for part in parts:
            if not part or part == '.':
                continue
            elif part == '..':
                if len(stack) > 1:  # 保留根目錄
                    stack.pop()
            else:
                stack.append(part)
        
        if len(stack) == 1:
            return '/'
        return '/'.join(stack)

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.simplifyPath("/a/./b/../../c/") == '/c'
    assert sol.simplifyPath("/home/") == "/home"
    assert sol.simplifyPath("/../../") == "/"
    assert sol.simplifyPath("/../") == "/"
    assert sol.simplifyPath("/a//b////c/d//././/..") == "/a/b/c"
    print("所有測試通過")

核心要點總結

• 棧語義完美契合：目錄層級天然對應棧結構
• 根目錄特殊處理：棧底預置空串，join 自然生成 / 開頭
• 多斜桿處理：split('/') 產生空串，統一忽略
• 邊界情況：.. 超過根目錄停在根、空路徑返回 /

路徑簡化是棧應用的教科書級範例，將字符串解析轉化為棧操作，邏輯清晰且易於擴展（如支持符號鏈接、權限檢查等）。