路径解析

GitHub跳转原题关系图Canvas 关系图返回列表

用目录组件栈处理绝对路径、相对路径、.、.. 与连续斜杠。

OJ: shumeng

题目 ID: CSP201604C

难度:入门

标签:字符串栈模拟

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 拆组件
    2. 绝对与相对路径
    3. 重新拼接
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定当前目录，对若干条路径做正规化：得到等价的不含 .、.. 和连续 / 的绝对路径。路径可能是绝对路径（以 / 开头）或相对路径；空路径表示当前目录；根目录的上一级仍是根目录。

思路

把路径按 / 切成一个个目录组件，用栈维护当前已经拼好的部分，一次扫描即可完成正规化。

拆组件

扫描路径时，遇到 / 就切出一段组件，连续斜杠自然产生空组件：

  • 空组件：跳过（对应连续斜杠或末尾斜杠）；
  • .：跳过（表示本目录）；
  • ..：弹出栈顶一层，栈为空时不动（根目录的上一级是它本身）；
  • 普通名字：压入栈。

绝对与相对路径

  • 绝对路径从根目录开始，栈初始为空；
  • 相对路径从当前目录开始，栈初始为当前目录的组件。

重新拼接

处理完所有组件后，用 / 把栈中元素连接起来；栈为空时输出唯一的根目录 /。

例如 /d1/./f1、/d1///f1 都会得到组件 d1, f1，输出 /d1/f1。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:48
 */
#include <bits/stdc++.h>
using namespace std;

// 把一段路径按 '/' 拆成目录组件，依次压入 parts 这个栈。
// '.' 与连续斜杠产生的空组件直接跳过；'..' 弹出栈顶一层（栈空时根目录的上一级还是根目录，不动）。
void append_path(vector<string> &parts, const string &path) {
    int start = 0;
    for (int i = 0; i <= (int)path.size(); i++) {
        if (i != (int)path.size() && path[i] != '/') {
            continue;
        }
        string part = path.substr(start, i - start);
        if (part == "..") {
            if (!parts.empty()) {
                parts.pop_back();
            }
        } else if (!part.empty() && part != ".") {
            parts.push_back(part);
        }
        start = i + 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int p;
    cin >> p;
    string current_directory;
    cin >> current_directory;
    cin.ignore(numeric_limits<streamsize>::max(), '\n'); // 丢弃当前目录一行的换行符，避免影响 getline

    // 当前目录本身是正规化绝对路径，预先拆成组件供相对路径使用
    vector<string> current_parts;
    append_path(current_parts, current_directory);

    while (p--) {
        string path;
        getline(cin, path);
        vector<string> parts;
        // 相对路径以当前目录为起点，绝对路径以根目录（空栈）为起点
        if (path.empty() || path[0] != '/') {
            parts = current_parts;
        }
        append_path(parts, path);

        if (parts.empty()) {
            cout << "/\n"; // 空栈对应根目录
        } else {
            for (int i = 0; i < (int)parts.size(); i++) {
                cout << '/' << parts[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

复杂度

  • 时间：每个字符只被扫描一遍，时间复杂度为 O(L)O(L)，其中 LL 为路径总长度。
  • 空间：栈最多保存一层组件，空间复杂度为 O(L)O(L)。

总结

连续斜杠和末尾斜杠都会产生空组件，统一跳过即可；.. 弹出时注意根目录没有上级，栈空时不做任何事。相对路径只需把初始栈换成当前目录的组件，其余处理完全相同。