# [71. Simplify Path](https://leetcode.com/problems/simplify-path/)
# 思路
题目要求简化unix的路径字符串。由题意知:
* `.` 代表当前目录，所以可忽略；
* `..` 代表上一个目录，所以应该进入上一个目录（即pop掉当前目录）；
* 连续多个`/`只代表一个`/`。     

因此我们可以根据以上规则，遍历一遍path字符串，用一个栈stk记录进入的文件夹名称，遍历完成后stk中即记录了简化后的路径名。     
根据如何通过path得到每个文件名，可分为两个思路: 双指针法和getline法。

## 思路一: 双指针法
定义两个指针low和high, low代表当前文件夹名称的第一个字符的前一个位置(所以肯定指向`/`), high代表当前文件夹名称的最后一个字符的位置。然后判断low和high之间组成的字符是否是`/.`或`/..`即可。例如:
```
path: //dir1/../
index:0123456789...
```
则第一次循环时, `low = 1, high = 5`, 其间组成的文件夹字符串为`/dir1`，不是`/.`或`/..`，应该将`/dir1`其push进stk；
第二次循环时，文件夹字符串为`/..`，应该将stk中的`/dir1`其pop出来；......      
时空复杂度均为O(n)

## 思路二: getline法
利用头文件string下的getline函数可以很方便的以`/`为分隔符将path分开，然后就和思路一类似了。     
C++中的getline用法可参考[此处](https://blog.csdn.net/MisterLing/article/details/51697098):
> 在C++中本质上有两种getline函数, 一种在头文件istream中，是istream类的成员函数, 另一种在头文件string中，是普通函数。这里我们用到的是第二种。

在头文件string中的getline函数有四种重载形式： 
``` C++
istream& getline (istream&  is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);
istream& getline (istream&  is, string& str);
istream& getline (istream&& is, string& str);
```
函数的变量：
```
is    ：表示一个输入流，例如cin。本题我们用到的是stringstream或者istringstream。
str   ：string类型的引用，用来存储输入流中的流信息。
delim ：char类型的变量，所设置的截断字符；在不自定义设置的情况下，遇到’\n’，则终止输入。
```
时空复杂度也都为O(n)    
注: 关于C++中的stringstream等输入输出流的用法可见[此处](https://www.cnblogs.com/gamesky/archive/2013/01/09/2852356.html)。     


  

# C++
## 思路一
``` C++
class Solution {
public:
    string simplifyPath(string path) {
        vector<string>stk;        
        int low = 0, high, len = path.size();
        string res = "";
        
        while(low < len){ // 每次循环得到一个文件夹的名称(以"/"开头, 例如"/.","/..","/a")
            while(low < len - 1 && path[low + 1] == '/') low++; 
            high = low + 1;
            while(high < len - 1 && path[high + 1] != '/') high++; 
            if(high == len) break;
            string dir = "";
            for(int i = low; i <= high; i++) dir += path[i]; // dir表示当前文件夹，以"/"开头
            if(dir == "/.."){
                if(!stk.empty()) stk.pop_back();
            }
            else if(dir != "/.") stk.push_back(dir);
            
            low = high + 1;
        }
        for(string dir: stk) res += dir;
        return stk.empty()? "/" : res;
    }
};
```
## 思路二
``` C++
class Solution {
public:
    string simplifyPath(string path) {
        string res, tmp;
        vector<string> stk;
        stringstream ss(path); // or istringstream ss(path);
        while(getline(ss,tmp,'/')) {
            if (tmp == "" or tmp == ".") continue;
            if (tmp == ".." and !stk.empty()) stk.pop_back();
            else if (tmp != "..") stk.push_back(tmp);
        }
        for(string str : stk) res += "/"+str;
        return res.empty() ? "/" : res;
    }
};
```