LeetCode 71. Simplify Path

71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

题目内容：
题目给出一个绝对路径，这个路径可能包括"/.."和"/."这些访问上一目录和当前目的部分，题目要求我们把这个这个路径做一个简化，输出一个跟输入路径意义相同，但简化过的路径字符串。

解题思路：
因为从左到右看一个路径的时候，如果遇到的是一个合法的文件夹，那么就相当于加深了一层目录，而遇到"/.."相当于返回上一个目录，这样的一个过程，跟stack的push和pop操作是类似的，所以在解决这道题的时候，我用了stack来帮助我记录’/’的位置，每当我访问到一个’/’，就把这个’/’的位置加到一个vector里面，此时有2种需要处理的情况：

1. 如果这个’/’与上一个’/’之间的字符串不是”..”，也不是”.”，那么就是往下进入了一个目录，可以把当前这个’/’的位置在vector中的索引压入栈中；
2. 如果这个’/’与上一个’/’之间的字符串是”..”，说明要放回上一层目录，此时只需要把栈顶元素推出；

直到遍历完整个字符串，此时stack中存储的就是最终要保留目录名称后面的’/’在vector中的索引。我们把这些’/’索引与上一个’/’之间的目录名称拼起来就可以得到结果。但是要注意，从stack中推出的’/’索引对应元字符串中’/’的顺序是反过来的。
下面再举个例子来解释这个算法的过程。
假如对于字符串 path="/a/./b/../../c/d/"，过程如下图：

到了最后，stack中剩下7和6这两个元素，vector中第[7-1]个和第7个元素分别是14和16，那么对应元字符串path中path(14, 16)对应的子串就是"d"；用同样的方法，我们通过栈的第二个元素找到目录"c"，把这两个目录名称拼起来就可以得到"/c/d"

代码：

class Solution {
public:
    string simplifyPath(string path) {
        vector<int> slicePos;
        stack<int> sliceIndex;
        string temp = "";
        string result = "";
        if (path[path.size() - 1] != '/') path += '/';
        for (int i = 0; i < path.size(); i++) {
            if (path[i] == '/') {
                slicePos.push_back(i);
                if (i != 0) {
                    if (temp == ".." && !sliceIndex.empty()) {
                        sliceIndex.pop();
                    }
                    else if (temp != "." && temp != ".." && temp != "") {
                        sliceIndex.push(slicePos.size() - 1);
                    }
                }
                temp = "";
            }
            else {
                temp += path[i];
            }
        }
        if (sliceIndex.empty()) result = "/";
        while (!sliceIndex.empty()) {
            int index = sliceIndex.top();
            sliceIndex.pop();
            result ="/" + path.substr(slicePos[index - 1] + 1, slicePos[index] - slicePos[index - 1] - 1) + result;
        }
        return result;
    }
};