简化路径

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simplify-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

路径简化并不算复杂，规则无非就几点：

保留一个斜杠，即不得有连续的/出现
/./表示本路径，可以使用/表示
/a/../中..表示上一层路径
其他都不需要处理

明显，解决问题的时候，只需要按照这个规则描述即可，不难发现我们只需要处理/和.的问题处理即可，那么很简单，只需要保证/前面没有/，而遇到点则处理。

不难发现，对于.来说，除了路径的最后，其前后都需要有/才生效，否则无任何效果。那么对于.的处理应该放在发现/的时候处理，而遇到.时，前面不是/则不予于理会。

不过我们需要一样东西来记录最终的答案，题目属于栈类的题目，我们可以使用栈来作为存储容器。

看代码:

class Solution {
public:
    string simplifyPath(string path) {
        string res;
        std::deque<char> deq;
        int dot_count{0};

        path += '/';

        for (size_t i{0}; i<path.size(); ++i) {
            char ch = path[i];
            switch (ch) {
                case '/':
                    if (0 != dot_count) {
                        if ('.' != path[i-1]) {
                            --i;
                            continue;
                        }

                        switch (dot_count) {
                            case 2: {
                                // 向前
                                int slash{0};
                                while (2 != slash && !deq.empty()) {
                                    if ('/' == *(deq.end() - 1)) {
                                        slash += 1;
                                    }
                                    deq.pop_back();
                                }
                                deq.push_back('/');
                                break;
                            }
                            case 1:
                                deq.pop_back();
                                break;
                            default:
                                break;
                        }
                        dot_count = 0;
                    }

                    if (!deq.empty() && '/' == *(deq.end() - 1)) {
                        deq.pop_back();
                    }
                    deq.push_back('/');
                    break;
                case '.':
                    if ('/' == *(deq.end() - 1)) {
                        deq.push_back('.');
                        dot_count = 1;
                        continue;
                    }
                    deq.push_back('.');
                    if (0 != dot_count) {
                        dot_count+=1;
                    }
                    break;
                default:
                    dot_count = 0;
                    deq.push_back(ch);
                    break;
            }
        }

        if (1 != deq.size() && '/' == *(deq.end()-1)) {
            deq.pop_back();
        }

        while (!deq.empty()) {
            res += *(deq.begin());
            deq.pop_front();
        }

        return res;
    }
};

用例跑完8ms，还算可以，超77%。

首先给原有的字符串添加了/在末尾，这是为了处理原字符串末尾没有/的情况，如果末尾是.，按照里面的代码的思路会将末尾的.忽略掉，最简单的办法是照一个可以被处理的符号在末尾，/很适合。

还有其他的解法，可以尝试将字符串分割，分隔标识符为/，那么最终需要处理的是.，似乎更加简单。

不过现在停留在栈的学习中，对于对应标签的题目尝试使用纯粹的题目来解题。

查看了下golang里面filepath中的Clean函数：

func Clean(path string) string {
    originalPath := path
    volLen := volumeNameLen(path)
    path = path[volLen:]
    if path == "" {
        if volLen > 1 && originalPath[1] != ':' {
            // should be UNC
            return FromSlash(originalPath)
        }
        return originalPath + "."
    }
    rooted := os.IsPathSeparator(path[0])

    // Invariants:
    //    reading from path; r is index of next byte to process.
    //    writing to buf; w is index of next byte to write.
    //    dotdot is index in buf where .. must stop, either because
    //        it is the leading slash or it is a leading ../../.. prefix.
    n := len(path)
    out := lazybuf{path: path, volAndPath: originalPath, volLen: volLen}
    r, dotdot := 0, 0
    if rooted {
        out.append(Separator)
        r, dotdot = 1, 1
    }

    for r < n {
        switch {
        case os.IsPathSeparator(path[r]):
            // empty path element
            r++
        case path[r] == '.' && (r+1 == n || os.IsPathSeparator(path[r+1])):
            // . element
            r++
        case path[r] == '.' && path[r+1] == '.' && (r+2 == n || os.IsPathSeparator(path[r+2])):
            // .. element: remove to last separator
            r += 2
            switch {
            case out.w > dotdot:
                // can backtrack
                out.w--
                for out.w > dotdot && !os.IsPathSeparator(out.index(out.w)) {
                    out.w--
                }
            case !rooted:
                // cannot backtrack, but not rooted, so append .. element.
                if out.w > 0 {
                    out.append(Separator)
                }
                out.append('.')
                out.append('.')
                dotdot = out.w
            }
        default:
            // real path element.
            // add slash if needed
            if rooted && out.w != 1 || !rooted && out.w != 0 {
                out.append(Separator)
            }
            // copy element
            for ; r < n && !os.IsPathSeparator(path[r]); r++ {
                out.append(path[r])
            }
        }
    }

    // Turn empty string into "."
    if out.w == 0 {
        out.append('.')
    }

    return FromSlash(out.string())
}

其主要重点也是在处理.和..，并不复杂，golang实现起来确实优雅。

Mark一个，可以仿照来做一个C++版本的。

[题目][栈] 简化路径

简化路径