simplify path.

simplify_path.cpp

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

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

class Solution {
public:
    //split string by /
    // for each substr, if not .., push to stack
    //      otherwise, pop
    // then from bottom to up is the path
    
    //Note: if the path is empty, change it to "/"
    void splitString(string &str, vector<string> &vStr, char separator) {
        //find occurance of separator
        int start = 0, end = 0;
        while ( (end = str.find(separator, start) ) != string::npos) {
            vStr.push_back(str.substr(start, end-start));
            start = end + 1;
        }
        vStr.push_back(str.substr(start));
    }
    string simplifyPath(string path) {
        int size = path.size();
        stack<string> myStack;
        vector<string> vStr;
        splitString(path, vStr, '/');
        
        for(int i=0; i<vStr.size(); i++) {
            string str = vStr[i];
            if (str.empty() || str == ".")
                continue;
            if (str != "..")
                myStack.push(str);
            else // .., pop up one level
            {
                if (!myStack.empty())
                    myStack.pop();
            }
        }
        
        //now connect all , after reversing to another stack
        //  a/b/c/d     --> myStack: (bottom to top) a b c d ; stack 2 (B to T): d c b a
        stack<string> stack2;
        while( !myStack.empty()) {
            stack2.push(myStack.top());
            myStack.pop();
        }
        
        //connect from stack2
        path = "";
        while (!stack2.empty()) {
            path += "/" +stack2.top();
            stack2.pop();
        }
        if (path.empty())
            path="/";
        return path;
    }
};