題目背景

本文將討論一道與操作系統路徑歸一化有關的問題，該問題來自 BerOS 文件系統 的設計。BerOS 是一個新型操作系統，其文件路徑系統允許路徑中的分隔符 / 重復出現。例如，以下路徑被視為等價的：

• /usr//local//nginx/sbin/
• /usr/local/nginx///sbin

為了優化文件系統操作，我們需要將路徑轉化為一種標準化形式，即：

1. 重復的 / 被合并為單個 /。
2. 結尾處的多余 / 被移除（如果路徑非根目錄）。
3. 保留路徑最小的 / 數量。

輸入輸出格式

輸入：

• 一行路徑字符串，路徑僅由小寫字母、字符 / 組成。
• 路徑始終以字符 / 開頭。
• 路徑長度不超過 100 個字符。

輸出：

• 標準化后的路徑。

示例：

輸入	輸出
//usr//local//nginx/sbin	/usr/local/nginx/sbin
/usr///local//	/usr/local

---

Python 實現代碼

以下是該問題的 Python 實現代碼，完整地解決了路徑歸一化的需求：

def main():# 輸入路徑path = input().strip()output = ""flag = False# 遍歷路徑中的每個字符for char in path:if char != '/' or not flag:  # 如果當前字符不是 '/' 或之前沒有連續的 '/'output += charflag = (char == '/')  # 記錄當前是否遇到 '/'# 去除路徑末尾多余的 '/'if flag and len(output) > 1:output = output[:-1]# 輸出標準化路徑print(output)if __name__ == "__main__":main()

---

代碼解析

1. 輸入讀取：

   • 使用 input().strip() 讀取用戶輸入并移除首尾多余空格。

2. 路徑標準化邏輯：

   • 遍歷路徑字符：
     • 如果當前字符不是 / 或前一個字符不是 /，將字符加入結果字符串。
     • 使用布爾變量 flag 跟蹤前一個字符是否為 /。

3. 末尾 / 處理：

   • 如果路徑以 / 結尾且長度大于 1（非根路徑），移除最后一個 /。

4. 輸出：

   • 打印標準化后的路徑。

---

測試結果

運行以下輸入測試，程序表現正常，輸出符合預期：

輸入: //usr//local//nginx/sbin
輸出: /usr/local/nginx/sbin

輸入: /usr///local//
輸出: /usr/local

---

算法復雜度分析

• 時間復雜度：O(n)，其中 n 為路徑字符串長度。程序僅遍歷字符串一次。
• 空間復雜度：O(n)，結果字符串需要額外存儲空間。

---

總結

本文介紹了一個經典的路徑歸一化問題及其高效的 Python 實現。代碼邏輯清晰、易于擴展，并在路徑標準化領域具有實際應用價值。如果你對本文感興趣，歡迎分享和討論！