71 Simplify Path

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

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

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".

Solution

class Solution {
public:
    string simplifyPath(string path) {
        path += '/';
        int n = path.size();
        string tmp = "";
        stack<string> s;
        for ( int i = 0; i <= n-1; i++ ) {
            if ( path[i] == '/' ) {
                if ( tmp == ".." and ! s.empty() ) s.pop();
                if ( tmp != "" and tmp != "." and tmp != "..") s.push(tmp);
                tmp = "";
            }
            else tmp += path[i];
        }
        string res = "";
        if ( s.empty() ) return "/";
        while ( ! s.empty() ) {
            res = "/" + s.top() + res;
            s.pop();
        }
        return res;
    }
};

Notes
Use a stack to record all the parts divided by /.

• If it is "..", pop out the top directory from s if it is not empty.
• If it is not "" and ".." and ".", push it to the stack.
• Note the trick to append a "/" at the end of the path, so that the last directory won't be missed. (It does not matter that we have multiple consecutive "/".)
• Note the corner case that the stack is empty after the treatment. (return "/" as the result)