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

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

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

很喜欢这道题，直接把Linux源码拿出来考了。

我不知道Linux源码是如何实现的，我的想法是用一个栈来存储每一层的文件夹名称。如果遇到”.”的话，就忽略。如果遇到”..”的话，就pop栈顶，代表返回上一层。

需要注意，它在corner case中提到，如果返回上一层超过了root的话，比如”/../”，则记为”/”。如果多个”//”重复出现的话，则只取一个”/”进行判断。

代码写的有点乱，这里我用了一个vector<string>来存储每一层的文件夹名称，不用stack的原因是vector可以在最后输出结果时提供从底到顶的遍历。

我用了isNewLayer来区分当前读取到的’/’是新文件夹名的结束还是旧文件夹名的开始。

C++代码如下

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> s;
        string re;
        size_t len = path.size();
        if(len == 1) return path;
        int start = 1; // start point to the first char of a new directory
        size_t i = 1;// warning: program may skip to line 73 directly
        bool isNewLayer = false;
        string layer;
        while(i < len){
            if(path[i] == '/'){
                //a new layer found
                if(isNewLayer == true){
                    isNewLayer = false;
                    layer = path.substr(start, i - start);
                    start = i + 1; //warning: start may exceed the range
                    //current layer, ignore it
                    if (layer == "."){
                        ;
                    }
                    //upper layer, pop one layer
                    else if(layer == ".."){
                        //no upper layer
                        if(s.empty()){
                            ;
                        }
                        else{
                            s.pop_back();
                        }
                    }
                    //a new layer name
                    else{
                        s.push_back(layer);
                    }
                }
                //not a new layer
                else{
                    start = i + 1; //warning: start may exceed the range
                }
            }
            //current char is not a '/'
            else{
                isNewLayer = true;
            }
            i++;
        }
        if(start < i){
            layer = path.substr(start, i - start);
            //current layer
            if(layer == "."){
                ;
            }
            //upper layer
            else if(layer == ".."){
                //root layer
                if(s.empty()){
                    ;
                }
                else{
                    s.pop_back();
                }
            }
            else{
                s.push_back(layer);
            }
        }
        for(size_t i = 0; i < s.size(); i++){
            re.push_back('/');
            re.append(s[i]);
        }
        if(s.size() == 0){
            re.push_back('/');
        }
        return re;
    }
};

有空看下Linux源码。