【栈应用】简化路径

题目描述：

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中

1. 一个点（.）表示当前目录本身；
2. 两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。
3. 任意多个连续的斜杠（即，‘//’）都被视为单个斜杠 ‘/’ 。
   注： 对于此问题，任何其他格式的点（例如，‘…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

1. 始终以斜杠 ‘/’ 开头。
2. 两个目录名之间必须只有一个斜杠 ‘/’ 。
3. 最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
4. 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
   返回简化后得到的 规范路径 。

示例：

解题思路：

本题是一道典型的用栈解决的问题，下面我们来简化一下这个问题

以 path = “/a/./b/…/…/c/” 为例，对这样的字符串 path 我们很难读取处理，而我们将其稍微简化为 a, b, … , … , c 这样的字符串数组，我们直接对每个文件名进行入栈出栈操作就会简单的多。遇见两个点…我们就将前一文件名字符串出栈，否则就将字符串数组入栈，最后进行整合即可。

1. 将字符串用 / 分割 —— Split(“/”)
   注：split遇到连续的分割符，会在第一个分割符以后分隔符位置返回一个空格存入返回数组，而不是忽视连续的分割符。分隔符在首位置时，会返回一空字符（“”）作为返回字符数组的0号元素。
2. 遍历字符数组，若当前字符数组不为空，判断其是否为“…”，是否为“.”，进行相应出入栈操作。

代码：

    public String simplifyPath(String path) {
        Deque<String> stack = new LinkedList<>();
        String[] str = path.split("/");
        for(int i=0; i<str.length; i++){
            // 栈不为空，且当前字符串为 .. ，前进一个目录
            if(!stack.isEmpty() && str[i].equals("..")){
                stack.removeLast();
            } else{
                // 字符串不为空，不为一个 . , 当前文件加入到栈中
                if(str[i].length() !=0 && !str[i].equals("..") && !str[i].equals(".")){
                    stack.addLast(str[i]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        // 整合过程
        sb.append("/");
        while(!stack.isEmpty()){
            sb.append(stack.removeFirst());
            if(stack.size() != 0){
                sb.append("/");
            }
        }
        return sb.toString();
    }
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