UVa12298 3KP-BASH Project

题目链接

  UVa12298 3KP-BASH Project

题意

  摘自 《算法竞赛入门经典：训练指南》刘汝佳，陈锋著。有删改。

  你的任务是为一个假想的 3KP 操作系统编写一个简单的 Bash 模拟器。由于操作系统本身还没有写完，你暂时需要在模拟器的内存中虚拟出一个文件系统，而不是和真实的文件系统交互。下面介绍 3KP 操作系统中的文件系统。
  文件（file）是数据存储的最小单位。文件名由英文字母（大小写敏感）、数字和点（.）组成，但不能包含两个连续的点。用户创建的文件名不能是单个的点字符（它代表当前目录）。文件名长度不能超过 255，文件大小不能超过 $2^{63}$。一个文件可能具有 directory 属性和 hidden 属性。
  目录（directory）是大小为 0 、具有 directory 属性的文件，里面可以保存任意数量的目录和文件。空文件系统只有一个文件，叫做“根目录”。在任意时刻，有一个称为“当前目录”的目录。 Bash 启动时，当前目录就是根目录。
  指令中引用文件的时候，可以使用绝对路径或者相对路径。绝对路径以字符/开头，如 /home/acm/uva ；相对路径不以字符 / 开头，当前目录和上层目录分别用 . 和 … 表示，如当前目录为 /home/acm/uva，那么相对路径 …/…/…/home/… 就是根目录。 你的 Bash 模拟器需要支持 8 个命令，具体如下表所示。

  命令行包含一条或多条命令，用管道符号 | 隔开（管道符号的前后不一定有空格）。第一条命令必须是除了 grep 之外的上述命令之一，而剩下的命令必须是 grep。如果违反上述规定，应输出 bad usage，并且不执行任何命令。输入不会在除了 grep 之外的其他命令中使用引号（原题未写，但书中是这么说的）。
  命令和参数、参数和参数之间用一个或多个空格隔开。每个命令的必选参数（如果有的话）不一定是第一个参数，可选参数可能在必选参数之前，且以任意顺序出现。如果用户忽略了必选参数，或传入了过多必选参数，应输出 bad usage 。但忽略传入的无效可选参数（如 mkdir a -h -h -h -h -abababab 等价于 mkdir a -h）。

输入格式

  输入包含多组数据，每组数据对应一次独立的 BASH 会话。数据的每行为一行命令（长度不超过 2048 个字符）。命令的参数之间可以有任意数量的空白字符。每次会话的最后一条命令保证为exit。输入结束标志为文件结束符（EOF）。假定每次会话开始时，文件系统为空，当前目录为根目录。

输出格式

  依次输出每行命令的输出（如果有的话）。

分析

  纯模拟题，很难 AC，洛谷题解上 ExplodingKonjac 说他耗时 346 天通过此题。贴上 ExplodingKonjac 的补充说明：

  文件名中只能包含大小写英文字母、数字、点号，且不可以是单个点号，也不能包含两个连续点号，长度不能超过 255。这句在题面中有，但是容易被忽视。执行 touch 和 mkdir 时文件或目录名违反上述规定要输出 bad usage（但如果文件文件或目录名之前的路径如果不存在要输出 path not found）。
  文件大小不能超过 $2^{63}$，违反该规定应当输出 bad usage。实测数据没有超过 $2^{63}$的，不过读取-size参数应该注意像 -100ch 这种要当数字提取成100，而 -ch100这种不能当数字。
  文件路径中两个斜杠之间可能是空的，这种东西表示当前路径。比如路径 .///././// 和路径 . 表示同一种东西。
  一个命令行中有由管道符号隔开的多个命令时，应该首先判断第一个命令不是 grep（是 grep 则直接输出 bad usage）才执行第一个命令。之后的命令必须都是 grep，否则直接输出 bad usage 而不执行第二个命令及以后的所有命令。 比如 mkdir a | tt | grep "cc"会先执行 mkdir a，然后输出 bad usage。
  管道符号和空格可能被引号所包含，你不能根据其分隔参数或命令。比如说，grep “ot fou” 不能被分隔成 grep、“ot、fou”。
  ls 命令中可能同时包含 -d 和 -f 参数，此时应该输出 [empty]。但是数据中不会同时包含 -s 和 -S。

AC 代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

#define ULL unsigned long long

const string no_such_command = "no such command", bad_usage = "bad usage", path_not_found = "path not found",
             file_not_found = "file not found", dir_exists = "a directory with the same name exists",
             f_dir_exists = "file or directory with the same name exists", empty_l = "[empty]";
struct params {ULL size = 0; bool r = false, h = false, s = false, S = false, f = false, d = false;};
struct file {
    string name, full_path; int parent; ULL size; bool dir, hidden; vector<int> sub;
    file(const string& name, const string& full_path, int parent, ULL size = 0, bool dir = false, bool hidden = false)
    :name(name), full_path(full_path), parent(parent), size(size), dir(dir), hidden(hidden) {};
};
vector<file> fs; int curr_dir;

void trim(string& s) {
    int l, r, t = s.size();
    for(l=0; l<t; ++l) if(!isspace(s[l])) break;
    for(r=t-1; r>l; --r) if(!isspace(s[r])) break;
    s = s.substr(l, r-l+1);
}

bool valid_path(const string& s, int& dir, string& name, bool pre = true) {
    vector<string> p; dir = s[0] == '/' ? 0 : curr_dir;
    if (!s.empty() && s.back() == '/') pre = false;
    for (int i=0, h=0, t=s.size(); i<t; ++i) {
        if (s[i] == '/') {
            if (i > 0 && s[i-1] != '/') p.push_back(s.substr(h, i-h));
            h = i+1;
        } else if (i+1 == t) p.push_back(s.substr(h, t-h));
    }
    for (int i=0, t=p.size()-pre; i<t; ++i) {
        if (p[i] == ".") continue;
        if (p[i] == "..") {
            if (fs[dir].parent < 0) return false;
            dir = fs[dir].parent;
        } else {
            const vector<int>& sub = fs[dir].sub; bool ok = false;
            for (int j=sub.size()-1; j>=0; --j) if (fs[sub[j]].name == p[i]) {
                if (fs[sub[j]].dir) dir = sub[j], ok = true;
                break;
            }
            if (!ok) return false;
        }
    }
    name = p.empty() || s.back() == '/' ? "" : p.back();
    return true;
}

bool valid_name(const string& s) {
    if (s.empty() || s.size() > 255) return false;
    for (int i=0, t=s.size(); i<t; ++i)
        if ((s[i]=='.' && (t==1 || (s[i+1]=='.'))) || (s[i]!='.' && !isalpha(s[i]) && !isdigit(s[i]))) return false;
    return true;
}

bool cmp_p(int i, int j) {
    return fs[i].full_path < fs[j].full_path;
}

bool cmp_s(int i, int j) {
    return fs[i].size < fs[j].size || (fs[i].size == fs[j].size && fs[i].full_path < fs[j].full_path);
}

bool cmp_S(int i, int j) {
    return fs[i].size > fs[j].size || (fs[i].size == fs[j].size && fs[i].full_path < fs[j].full_path);
}

void visit_fs(int dir, vector<int>& out, const string& name, bool r, bool h, bool d = true, bool f = true) {
    for (int i=0, t=fs[dir].sub.size(); i<t; ++i) {
        const file& fi = fs[fs[dir].sub[i]];
        if ((!fi.hidden || h) && ((fi.dir && d) || (!fi.dir && f)) && (name.empty() || fi.name == name))
            out.push_back(fs[dir].sub[i]);
        if (fi.dir && r) visit_fs(fs[dir].sub[i], out, name, r, h, d, f);
    }
}

string info(const file& f) {
    ostringstream ss; ss << f.full_path << ' ' << f.size;
    if (f.hidden) ss << " hidden";
    if (f.dir) ss << " dir";
    return ss.str();
}

void new_session() {
    fs.clear(); fs.push_back(file("", "/", -1, 0, true)); curr_dir = 0;
}

void cd(const string& mp, vector<string>& out) {
    int dir; string name;
    if (!valid_path(mp, dir, name, false)) return out.push_back(path_not_found);
    curr_dir = dir;
}

void touch(const string& mp, const params& p, vector<string>& out) {
    int dir; string name;
    if (!valid_path(mp, dir, name)) return out.push_back(path_not_found);
    if (!valid_name(name)) return out.push_back(bad_usage);
    for (int i=fs[dir].sub.size()-1; i>=0; --i) if (fs[fs[dir].sub[i]].name == name) {
        if (fs[fs[dir].sub[i]].dir) return out.push_back(dir_exists);
        fs[fs[dir].sub[i]].size = p.size; fs[fs[dir].sub[i]].hidden = p.h;
        return;
    }
    file fi(name, (dir ? fs[dir].full_path + '/' : "/") + name, dir, p.size, false, p.h);
    int s = fs.size(); fs[dir].sub.push_back(s); fs.push_back(fi);
}

void mkdir(const string& mp, const params& p, vector<string>& out) {
    int dir; string name;
    if (!valid_path(mp, dir, name)) return out.push_back(path_not_found);
    if (!valid_name(name)) return out.push_back(bad_usage);
    for (int i=fs[dir].sub.size()-1; i>=0; --i) if (fs[fs[dir].sub[i]].name == name)
        return out.push_back(f_dir_exists);
    file fi(name, (dir ? fs[dir].full_path + '/' : "/") + name, dir, 0, true, p.h);
    int s = fs.size(); fs[dir].sub.push_back(s); fs.push_back(fi);
}

void find(const string& mp, const params& p, vector<string>& out) {
    int dir; string name;
    if (!valid_path(mp, dir, name)) return out.push_back(path_not_found);
    vector<int> res;
    visit_fs(dir, res, name, p.r, p.h);
    if (res.empty()) return out.push_back(file_not_found);
    sort(res.begin(), res.end(), cmp_p);
    for (int i=0, t=res.size(); i<t; ++i) out.push_back(info(fs[res[i]]));
}

void ls(const string& mp, const params& p, vector<string>& out) {
    int dir; string name;
    if (!valid_path(mp, dir, name, false)) return out.push_back(path_not_found);
    vector<int> res;
    visit_fs(dir, res, "", p.r, p.h, !p.f, !p.d);
    if (res.empty()) return out.push_back(empty_l);
    sort(res.begin(), res.end(), p.s ? cmp_s : (p.S ? cmp_S : cmp_p));
    for (int i=0, t=res.size(); i<t; ++i) out.push_back(info(fs[res[i]]));
}

void run_command(const string& cmd, vector<string>& out) {
    if (cmd.empty()) return;
    istringstream ss(cmd); string s; ss >> s;
    if (s != "cd" && s != "touch" && s!= "mkdir" && s != "find" && s != "ls" && s != "pwd" && s != "exit" && s != "grep") {
        out.push_back(no_such_command);
    } else {
        string mp; params p; ULL v; string s1; ss >> s1;
        while (!s1.empty()) {
            if (s1[0] == '-') {
                if (isalpha(s1[1])) {
                    if (s1[1] == 'r') p.r = true;
                    else if (s1[1] == 'h') p.h = true;
                    else if (s1[1] == 'd') p.d = true;
                    else if (s1[1] == 'f') p.f = true;
                    else if (s1[1] == 's') p.s = true;
                    else if (s1[1] == 'S') p.S = true;
                } else if (istringstream(s1.substr(1)) >> v) p.size = v;
                else return out.push_back(bad_usage);
            } else if (!mp.empty()) return out.push_back(bad_usage);
            else mp = s1;
            s1.clear(); ss >> s1;
        }
        if (s == "cd") mp.empty() ? out.push_back(bad_usage) : cd(mp, out);
        else if (s == "touch") mp.empty() ? out.push_back(bad_usage) : touch(mp, p, out);
        else if (s == "mkdir") mp.empty() ? out.push_back(bad_usage) : mkdir(mp, p, out);
        else if (s == "find") mp.empty() ? out.push_back(bad_usage) : find(mp, p, out);
        else if (s == "ls") ls(mp, p, out);
        else if (s == "pwd") out.push_back(mp.empty() ? fs[curr_dir].full_path : bad_usage);
        else if (s == "grep" || (s == "exit" && !mp.empty())) out.push_back(bad_usage);
        else new_session();
    }
}

void run_cmdline(const string& line) {
    vector<string> cmds, out;
    for (int i=0, t=line.size(), s=0, q=0; i<=t; ++i) if (i==t || (line[i] == '|' && !q)) {
        cmds.push_back(string(line.begin()+s, line.begin()+i)); s = i+1;
    } else if (line[i] == '"') q ^= 1;
    if (cmds.empty()) return;
    run_command(cmds[0], out);
    for (int i=1, t=cmds.size(); i<t; ++i) {
        istringstream ss(cmds[i]); string s, p; ss >> s; getline(ss, p); trim(p);
        if (s != "grep" || p.size() < 2 || p[0] != '"' || p.back() != '"') {
            cout << bad_usage << endl;
            return;
        }
        if (out.empty() || p.size()==2) continue;
        vector<string> filtered; s = p.substr(1, p.size()-2);
        for (int j=0, k=out.size(); j<k; ++j) if (out[j].find(s) != string::npos) filtered.push_back(out[j]);
        out.swap(filtered);
    }
    for (int i=0, t=out.size(); i<t; ++i) cout << out[i] << endl;
}

int main() {
    string line; new_session();
    while (getline(cin, line)) run_cmdline(line);
    return 0;
}