CCF 路径解析 满分代码(两种解法） + 解题思路 + 技巧总结 201604

解法） + 解题思路 + 技巧总结 201604"/>

CCF 路径解析 满分代码(两种解法） + 解题思路 + 技巧总结 201604

题目描述

解题思路

数据范围很小，只需要考虑暴力模拟实现
将不规范的路径规范化，就是需要使路径没有 ‘.’ 、没有多余的 ‘/’
（代码实现1是用workmore函数对读入的串先进行去除多余/,在workpoint函数里边将字符串根据/进行划分，边处理./…问题）
（代码实现2是在get函数里边将字符串根据/进行划分，边处理多余/问题， 用order函数处理./…问题）
路径的存储可以利用substr将用/分隔的部分存储到vector数组或者stack中（方便…操作的弹出）

路径分为绝对路径和相对路径
如果是绝对路径，就是根据给出的文件路径处理
如果是相对路径，需要在遍历时加上初始的当前目录，以便返回上一级

'.'表示当前目录，则不处理，跳过
'…'表示返回上一级，则将存储路径的vector数组进行popback()或者stack的pop（）
其余的pushback() / push到路径数组后
最后将保存的路径输出就是答案

代码实现1

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <stack>using namespace std;stack <string> cur;stack <string> work(string str) //正规化路径
{stack <string> res;res.push("/");for (int i = 1; i < str.size(); i ++){int j = i;string t;while (j < str.size() && str[j] != '/') t += str[j ++];res.push(t);i = j;}return res;
}void workmore(string &str) //去除多余的/
{string t;for (int i = 0; i < str.size(); i ++){if (str[i] != '/' || i == 0) t += str[i];else if (i > 0 && str[i - 1] != '/') t += str[i];}str = t;
}void workpoint(stack <string> &res, string str)
{//cout << str;for (int i = 1; i < str.size(); i ++){int j = i;string t;while (j < str.size() && str[j] != '/') t += str[j ++];i = j;if (t == ".") continue;else if (t == ".."){if (res.size() > 1) res.pop();}else res.push(t);}
}void print(stack <string> t)
{if (t.size() == 1){cout << "/" << endl;return ;}vector <string> res;int cnt = 0;while (t.size() > 1){res.push_back(t.top());t.pop();cnt ++;}for (int i = cnt - 1; i >= 0; i --){cout << "/" << res[i];}cout << endl;
}int main()
{int n;cin >> n;string str;cin >> str;cur = work(str);getchar();while (n --){str = ""; //要想读取str等于空的情况，必须每次读取前清空strstack <string> res;getline(cin, str);if (str == "") //路径为空字符串{print(cur);continue;}workmore(str); //去除多余/if (str[0] == '/') //绝对路径{res.push("/");}else //相对路径,还是那个老毛病，题目中说的是不以/开头，但是不代表一定像样例一样以点开头，{   //当样例过不了的时候，一定再仔细看题，思考它的逻辑，肯定是某个方面理解错了，或者范围想小了//千万不要被样例所迷惑，其他测试样例可能还有很多情况res = cur;str.insert(0, "/"); //将相对路径前加一个/，和绝对路径统一格式，因为res里面已经保存了当前位置//所以也可以将当看成是绝对路径进行处理}workpoint(res, str); //去除内部点号print(res); //输出答案}return 0;
}

代码实现2

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;vector <string> get(string str) //将字符串以/为分隔存入vector数组中
{vector <string> res;for (int i = 0; i < str.size(); i ++){if (str[i] == '/') continue;int j = i + 1;while (j < str.size() && str[j] != '/') j ++;res.push_back(str.substr(i, j - i));i = j;}return res;
}void order(vector <string> cur, vector <string> path) //遍历给出的文件路径
{for (auto p : path){if (p == ".") continue; //表示当前目录，跳过不处理if (p == "..") //表示返回上一目录{if (cur.size()) //若当前目录不为空{cur.pop_back(); // 则返回上一目录，否则跳过不处理}}else{cur.push_back(p); // 如果是其他的，则遍历，假如当前目录}}if (cur.empty()) //如果遍历完，当前目录为空，只需要输出根目录{puts("/");return ;}for (auto s : cur) //如果路径不为空，则输出{cout << '/' << s;}cout << endl;return ;
}int main()
{int n;string str;cin >> n >> str;auto cur = get(str);vector <string> bn;getchar(); //使用getline前用了cin，需要用getchar过滤回车while (n --){vector <string> path;getline(cin, str); //由于cin无法读入空串，所以使用getline读入path = get(str);if (str.size() && str[0] == '/') order(bn, path); //遍历绝对路径else order(cur, path); //遍历相对路径}return 0;
}

技巧总结

• str.substr(i, j)可以从str下标为i的位置截取长度为j的字符串
• vector数组可以模拟栈，利用popback 和 pushback
• str.insert(i, “abc”)可以从str下标为i的位置插入字符串abc，记得此处只能插入字符串，要用双引号