你好，同学。欢迎来到 NOI 专题训练。今天我们要处理的是一个经典的字符串处理与栈结构综合应用题：简化路径。

在 Unix 操作系统中，路径管理是核心功能之一。这道题不仅考察你对字符串切分的熟练度，更考查你如何利用栈（Stack）维护层级关系。

---

一、 预备知识点

1. 栈（Stack/Vector）：用于维护目录的层级。因为我们需要“进入”和“返回”目录，符合后进先出的逻辑，但最后输出时需要从底向上遍历，故推荐使用 std::vector<string> 或 std::deque<string>。
2. 字符串处理：
   • std::string::find 或自定义双指针进行字符串切分（Split）。
   • 字符串拼接与子串提取。
3. Unix 路径规则：
   • . 代表当前目录（无视）。
   • .. 代表上一级目录（出栈）。
   • 多个连续斜杠 // 视为单个斜杠 /。

---

二、 NOI 竞赛题目描述

题目名称：简化路径 (Simplify Path) 时间限制：1.0s 内存限制：256MB

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

在 Unix 风格的文件系统中，规范路径应遵循以下规则：

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

【输入格式】 输入仅一行，包含一个长度为 $L$ 的字符串 path。

【输出格式】 输出一行，表示简化后的规范路径。

【样例输入 1】

/home/

【样例输出 1】

/home

【样例输入 2】

/../

【样例输出 2】

/

【样例输入 3】

/home//foo/

【样例输出 3】

/home/foo

【样例输入 4】

/a/./b/../../c/

【样例输出 4】

/c

【数据规模与约定】

• $1 \le L \le 3000$
• path 由英文字母，数字，'.'，'/' 或 '_' 组成。
• path 是一个有效的 Unix 风格绝对路径。

---

三、 启发式思路引导：草稿纸上的推演

请拿出草稿纸，我们通过“层级模拟法”来思考：

1. 核心矛盾：如何处理“返回”？

• 观察：路径中如果出现 dir_A/dir_B/..，实际上 dir_B 和 .. 会抵消，最后停在 dir_A。
• 启发：这就像是在做一个“入栈”和“出栈”的游戏。遇到正常的目录名就“进”，遇到 .. 就“出”。

2. 处理过程推演（以样例 4 为例）

路径：/a/./b/../../c/

1. 切分：按照 / 切分，得到元素序列：["a", ".", "b", "..", "..", "c"]。
2. 维护一个栈 S：
   • 遇到 a：入栈。 S = {a}
   • 遇到 .：当前目录，不做任何事。
   • 遇到 b：入栈。 S = {a, b}
   • 遇到 ..：弹栈。 S = {a}
   • 遇到 ..：弹栈。 S = {}
   • 遇到 c：入栈。 S = {c}
3. 结果生成：将栈中元素用 / 连接，并在开头加 /。结果为 /c。

3. 特殊情况思考

• 如果栈已经空了，又遇到 .. 怎么办？（比如 /../）
  • 结论：在根目录下 .. 依然留在根目录。即：如果栈为空，跳过 ..。
• 如果切分后得到空字符串（比如 //）怎么办？
  • 结论：直接忽略。

---

四、 算法流程图（伪代码逻辑）

在 C++14 中，建议使用 std::vector<string> 来模拟栈，因为它方便最后从底向上拼接字符串。

graph TD
    Start{开始处理路径} --> Init(初始化 Vector 变量 stk)
    Init --> Split(将路径按斜线分割为字符串列表 items)
    Split --> Loop{遍历 items 中的每一个元素 item}
    Loop -- 元素为空 或 item 等于点号 --> Next(跳过继续)
    Loop -- item 等于双点号 --> PopCheck{stk 是否为空}
    PopCheck -- 不为空 --> DoPop(弹出 stk 栈顶元素)
    PopCheck -- 为空 --> Next
    Loop -- item 是正常目录名 --> DoPush(将 item 压入 stk)
    DoPop --> Next
    DoPush --> Next
    Next --> LoopEnd{遍历结束}
    LoopEnd --> EmptyCheck{stk 是否为空}
    EmptyCheck -- 是 --> Root(返回根目录斜杠)
    EmptyCheck -- 否 --> Join(遍历 stk 元素并用斜杠连接)
    Join --> Result(输出最终生成的路径串)

---

五、 复杂度分析与优化建议

• 时间复杂度：$O(L)$。
  • 我们需要遍历一次原始字符串进行切分。
  • 我们需要遍历一次切分后的列表进行入栈出栈。
  • 最后遍历一次栈构造结果。
  • 所有操作都是线性级别的。
• 空间复杂度：$O(L)$。
  • 最坏情况下（如 /a/b/c/...），栈需要存储所有目录名，空间与路径长度成正比。

优化建议： 在 NOI 考场上，为了追求极致速度，可以不使用 stringstream。建议使用双指针法扫描字符串，当遇到非 / 字符时记录起点，遇到下一个 / 时截取子串。这样可以减少不必要的内存分配。

---

六、 读题关键词总结

在处理文件路径类题目时，请圈出以下关键词：

1. 绝对路径：意味着结果必须以 / 开头。
2. .. (双点)：这是“弹栈”信号，需注意栈空时的边界处理。
3. 多余斜杠：提示你在切分字符串时，要过滤掉长度为 0 的子串。
4. 规范路径格式：规定了结尾不能有斜杠（除非是根目录），这是输出时的格式检查点。

教练寄语：字符串题目往往不难，但逻辑细节多。在纸上写下栈的每一变动过程，能帮你规避 90% 的 Bug。去实现它吧！