最近在做与Unix/Linux的简化路径（simplify path）或称清理路径（clean path）有关的工作，刚刚好碰到这类问题，记录一下。

题目

地址：LeetCode 71. 简化路径

题目描述

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/' 。
• 最后一个目录名（如果存在）不能 以 '/' 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
  返回简化后得到的 规范路径 。

示例1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。 

示例2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例3：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例4：

输入：path = "/a/./b/../../c/"
输出："/c"

提示：

输入：path = "/a/./b/../../c/"
输出："/c"

提示：

• 1 <= path.length <= 3000
• path 由英文字母，数字，'.'，'/' 或 '_' 组成。
• path 是一个有效的 Unix 风格绝对路径。

解题思路

题目什么意思？
换上Unix/Linux，然后通过cd 指令进入指定路径，然后用pwd查看，就明白了。。目的就是要去掉路径中的"."".."成分，还有多余的（连续）"/"，以及末尾的"/"。比如，"/usr/./.././user//../user/test/hello/"，简化后应该为"/usr/test/hello"。

path是绝对路径，必定以"/"开头。将path按"/"（路径分隔符）进行切割，最近的两个"/"中间内容，就是一个路径组件（string component），用一个双向链表list components存储各有效component（不含"/"）。如果component，

1. 是"."，代表当前目录，直接忽略；

2. 是".."，代表父目录，正常情况是要弹出components的最后一个元素，即回到上一级目录。
   但有一种特殊情况，那就是已经没有上一级目录，即当前就是根目录（"/"），此时忽略即可。
   什么时候代表当前是根目录？components为空，目前没有任何路径组件。

3. 其他情况，代表正常路径组件，直接存入链表components即可。

此时，链表components存放的是各路径组件，已经排除掉"." ".."这样的相对路径符号，以及路径分隔符 "/"。剩下的工作，就是将各个组件重新组装成一个完整Unix风格路径。注意，除了最后一个路径组件，其余组件后面在组装时，都要加上一个路径分隔符。 比如，"/user/./.././user/./../user/./hello/././test" ，切割后得到链表components为{"user", "hello", "test"}，组装成完整路径，就是"/user/hello/test"

string simplifyPath(string path) {
    string absoluteRootPath = "/";
    if (path == absoluteRootPath) return path;

    // Split path with '/'
    std::list<string> components;
    size_t start = absoluteRootPath.size();
    size_t end;

    do {
        end = path.find_first_of("/", start);
        string curComponent;

        // curComponent is a sub-string nearest two '/' of path
        if (end == string::npos) {
            curComponent = path.substr(start);
        }
        else {
            curComponent = path.substr(start, end - start);
        }
        if (curComponent.empty() || curComponent == ".") { // ignore "."
        }
        else if (curComponent == "..") {
            if (!components.empty()) {
                components.pop_back();
            }
            else {
                // We have reach the root directory now, no need to remove ".."
            }
        } 
        else {
            components.push_back(curComponent);
        }

        if (end == string::npos) 
            break;
        start = end + 1;
    } while (start < path.size());

    stringstream ss;
    ss << absoluteRootPath;
    for (auto it = components.begin(); it != components.end(); ++it) {
        if (it != components.begin())
            ss << '/';
        ss << *it;
    }
    return ss.str();
}

题目变种

假如参数path不一定是绝对路径，可能是相对路径，怎么办？
比如path = ./martin/./../martin/book/

参数path是相对路径，跟绝对路径，解析的基本思路是一样的，不过有细微区别：
1）首先返回的路径，就不可能是绝对路径了，也是一个相对路径，用默认的当前路径"."作为缺省值。

2）在碰到".."回到上一级目录时，如果链表components为空，如何处理？
在path为绝对路径时，我们是直接忽略，因为已经达到根目录"/"。
在path为相对路径时，在当前函数无法直接解析，可以存入，因为相对路径通常是基于当前工作目录的，而当前工作目录并未在该函数内体现。

3）切割完路径后，如果得到的链表components为空，如何处理？
在path为绝对路径时，是返回根目录"/"。
在path为相对路径时，显然不能返回根目录，因为通常，也要基于当前工作目录，可以直接返回缺省的"."。

std::string simplifyPath(const std::string& path, const char outputSeparator)
{
    enum class PathType { kRelativePath = 0, kAbsolutePath };

    const std::string curRelativePath = ".";
    if (path.empty() || path == ".")
        return curRelativePath; // default path

    PathType pathType;
    // Find the root for absolute path
    std::string absoluteRootPath;
    // On Unix/Linux, root path is '/'
    if (path[0] == '/') { // absolute path
        absoluteRootPath = '/';
        pathType = PathType::kAbsolutePath;
    }
    else { // relative path
        pathType = PathType::kRelativePath;
    }

    // Split the path
    std::list<std::string> components; // every element is a path component, not including separator
    if (path.size() >= absoluteRootPath.size() + 1) {
        size_t start, end;
        if (absoluteRootPath.empty()) // path is relative path
            start = 0;
        else // path is absolute path, include a "/", need to ignore
            start = absoluteRootPath.size();

        do {
            end = path.find_first_of("/", start); // find from path[start, ...), any char is ok

            std::string curComponent;
            if (end == std::string::npos)
                curComponent = path.substr(start); // path[start, ...)
            else
                curComponent = path.substr(start, end - start); // path[start, end)

            if (curComponent.empty() || curComponent == ".") {// ignore "" and "."
            }
            else if (curComponent == "..") { // components will shrink when current component is ".."

                if (pathType == PathType::kAbsolutePath) { // absolute path
                    if (!components.empty()) {
                        // move to parent directory by removing "..", 
                        // if we do not stay at root directory now
                        components.pop_back();
                    }
                    else {
                        // We have reached root directory now, no need to remove "..", 
                        // so ignore this case
                    }
                }
                else { // relative path
                    if (!components.empty() && (components.back() != "..")) {
                        // move to parent directory if we can resolve previous component
                        components.pop_back();
                    }
                    else {
                        // We can not resolve previous component, 
                        // as it is empty or ".."
                        components.push_back(curComponent);
                    }
                }
            }
            else {
                components.push_back(curComponent);
            }

            if (end == std::string::npos) // there is no path segment left to split
                break;
            start = end + 1; // update start to next position

        } while (start < path.size());
    }

    // param path is relative path, and all components are removed.
    // so return a default path.
    if (components.empty() && pathType == PathType::kRelativePath) {
        return curRelativePath;
    }

    // package all path components from components to a new path
    std::stringstream ss;
    ss << absoluteRootPath;
    for (auto it = components.begin(); it != components.end(); ++it) {
        if (it != components.begin())
            ss << outputSeparator;

        ss << *it;
    }

    return ss.str();
}