如何用栈简化 Unix 文件路径？

简化版

简化 Unix 路径可以按 / 切分路径，用栈保存有效目录名。遇到空串或 . 忽略，遇到 .. 就弹出上一层目录，普通目录入栈，最后用 / 拼回绝对路径。

详细版

路径中的多个 / 等价于一个分隔符，. 表示当前目录，.. 表示回到上一级。因为“回到上一级”要撤销最近进入的目录，天然适合用栈。

String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();
    for (String part : path.split("/")) {
        if (part.length() == 0 || part.equals(".")) continue;
        if (part.equals("..")) {
            if (!stack.isEmpty()) stack.pollLast();
        } else {
            stack.offerLast(part);
        }
    }
    return "/" + String.join("/", stack);
}

绝对路径不能越过根目录，所以栈为空时遇到 .. 直接忽略。目录名如 ...、a.. 都是普通目录，不要误判。

完整版教学

一、路径简化在简化什么

Unix 绝对路径以 / 开头，目标是得到规范形式：只保留一个根 /，目录之间只有一个 /，不包含 . 和可以抵消的 ..。例如 /a//b/./../c/ 简化后是 /a/c。

/a//b/./../c/
  a  b  .  .. c
进入 a -> 进入 b -> . 不动 -> .. 退出 b -> 进入 c
结果 /a/c

这个过程本质上是在维护“当前路径上的目录栈”。

二、为什么用栈而不是字符串反复删除

.. 的语义是删除最近进入的一个有效目录，符合后进先出。若用字符串反复查找最后一个 / 再截断，代码容易在多个斜杠、根目录、尾部斜杠上出错。栈把状态拆得更干净：普通目录入栈，返回上一级出栈。

对于 /home/user/docs/..，最后的 .. 只影响 docs，不会影响更早的 home 或 user。这正是栈顶代表最近目录的原因。

三、四类 token 如何处理

按 / 切分后，可能出现四类片段：

片段	含义	处理
空串	多个 `/` 或首尾 `/` 产生	忽略
`.`	当前目录	忽略
`..`	上一级目录	栈非空则弹出
其他字符串	真实目录名	入栈

注意 ... 不是 ..，a.b 也不是特殊符号，它们都应作为普通目录名入栈。

四、根目录边界怎么处理

绝对路径不能退到根目录以上。比如 /../a 简化后是 /a，开头的 .. 被忽略，因为当前已经在根目录。对应到栈逻辑，就是栈为空时遇到 .. 不做任何事。

path = "/../../x"
栈初始 []
.. -> 空栈，忽略
.. -> 空栈，忽略
x  -> 入栈 [x]
结果 /x

这个边界是面试中最常见的错点之一。

五、拼接结果时注意什么

栈中按从根到当前目录的顺序保存目录名。Java 中可以用 offerLast 入队尾、pollLast 弹队尾，这样遍历栈时就是从根到叶。最终结果是根斜杠加上目录名用 / 连接。

if (stack.isEmpty()) return "/";
return "/" + String.join("/", stack);

若栈为空，"/" + String.join("/", stack) 在 Java 中也会得到 /，但显式说明空栈含义更利于面试解释。

六、常见误区与追问

记忆钩子：路径栈里只放“真的走进去的目录”。. 没走，空串没走，.. 是从最近走进去的目录退出来。

误区：看到包含两个点的字符串就弹栈。 只有片段严格等于 .. 才表示上一级，... 是普通目录名。
误区：根目录遇到 .. 也弹。 栈为空时没有上一层，绝对路径不能越过根目录。
误区：直接按字符逐个处理更简单。 字符处理容易混淆连续 / 和目录名，按片段处理更清晰。
追问：相对路径能用同样逻辑吗？ 可以借鉴，但相对路径开头的 .. 不能随便丢弃，因为它表示相对父目录。
追问：时间复杂度是多少？ 切分和遍历总长度为 n，拼接也为 n，所以 O(n)，额外空间 O(n)。
追问：为什么用 Deque 而不是旧的 Stack？ Deque 是更现代的栈接口，ArrayDeque 性能通常更好。

七、加强记忆

简化路径就是把路径动作翻译成栈动作：目录名入栈，.. 出栈，. 和空片段跳过。最后栈里剩下的就是从根到目标位置的规范路径。边界只记两条：空栈不能再退，... 不是 ..。

简化版

详细版