1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132


#include <iostream>
#include <vector>
#include <stack>

using namespace std;


//path: an absolute path for a file (Unix-style)
string SimplifyPath(string path) 
{
    path.push_back('/');//make sure the last path would be push to stack
    stack<size_t> iStack; //index of each directory in the path
    size_t pos = 0; //position for next directory to append
    iStack.push(pos);

    //since the path is absolute, the first character would always be '/' 
    for (int i = 1; i < path.size(); ++i)
    {
        char c = path[i];
        if (c != '/')
        {
            path[++pos] =c;
            continue;
        }

        if(path[i-1] == '/') continue;
        
        path[++pos] = c;// c == '/'
        int dir = iStack.top();
        if (path[dir+1]  == '.')
            switch (path[dir+2])
            {
                //stay in current directory
                case '/': pos = dir; break;
                    
                case '.':
                    if (path[dir+3] != '/') //hiden file
                        iStack.push(pos);
                    else
                    {
                        //back to the position of previous directory
                        if(iStack.size() > 1) iStack.pop();
                        pos = iStack.top();
                    }
                    break;
                    
                default: //hiden file
                    iStack.push(pos);
                    break;
            }
        else //simple directory
            iStack.push(pos);
    }

	if (pos == 0)pos = pos+1; //the path is back to the root
	
    path.erase(pos);
    return path;
}

//this method using a vector to save each directories
//path: an absolute path for a file (Unix-style)
string SimplifyPath2(string path) 
{
    vector<string> pathStack;
    string directory;
    path.push_back('/');//make sure the last path would be push to stack

    for (int i = 0; i < path.size(); ++i)
    {
        char c = path[i];
        if (c != '/')
        {
            directory.push_back(c);
            continue;
        }
        
        if (directory.size() <=0) continue;
       
        if (directory[0] == '.')
        {
            if (directory.size() > 1)
            {
                if(directory[1] == '.')
                {   
					if (directory.size() > 2) //hiden file
                        pathStack.push_back(directory);
                    else
						if (pathStack.size() > 0)
							 pathStack.pop_back();
				}
                        //go to parent path
                else //hiden file
                    pathStack.push_back(directory);
            }
            //else //go to current path, do nothing
        }
        else //simple path
            pathStack.push_back(directory);

        directory.clear();
    }

    path.clear();
    for (int i = 0; i < pathStack.size(); ++i)
        path += '/' + pathStack[i];

	if (path.size() <=0 )path = "/";

    return path;
}


int main(int argc, char** argv)
{
	string s = "/home/../..";
    cout << s << " => " << SimplifyPath(s) << endl;
	s = "/a/./.b/../../c/";
    cout << s << " => " << SimplifyPath2(s) << endl;
	s = "/home/of/foo/../../bar/../../is/./here/.";
    cout << s << " => " << SimplifyPath2(s) << endl;
/**
 
 /home/../.. => /
 /a/./.b/../../c/ => /c
 /home/of/foo/../../bar/../../is/./here/. => /is/here

 **/
	
	
    return 0;
}
View Program Text


Test Status