【UVA10966】3KP-BASH Project

Author Avatar
mrsrz 10月 12, 2019

毒瘤大模拟

题目大意：

让你写一个 bash。需要支持cd,mkdir,touch,find,ls,pwd,exit,grep这些命令。

更具体的要求见题面。

题解：

实现起来不难，细节非常多。而且很多地方题目里并没有提到。前前后后花了我 3 天。

由于有管道，一行里会有很多命令。所以需要先分离命令。

然后每条命令里有必选参数和若干可选参数，也可以分离出来。

接下来各个命令的具体实现部分还是比较简单的。

主要是在处理一些不合法操作的时候，有很多坑点。这里列举几个：

  • 管道符号可能被引号包含。

  • ls命令会同时有-f和-d参数，此时应输出[empty]。

  • 命令a |应输出bad usage而不是no such command。

  • 路径/./././//./表示当前目录，即两个斜杠中间为空时，和.同一个效果。

  • 可能有多个必选参数，此时输出bad usage。

由于题意描述非常不清晰，因此有些地方的判断并不保证绝对正确，可能只是数据中没有。我也没什么办法

Code：

/*
By mrsrz
2019-10-10 ~ 2019-10-12
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const LL inf=1uLL<<63|1;
/*
 * 基本框架：
 * 文件存储结构的实现
 * 对命令分别进行处理
 * 对参数的分离及判断
 * Update on 2019-10-11
 * 原来对命令的处理太乱，现在决定使用分裂各部分（命令，必选参数，可选参数）
 */

inline void erase_space(string&s){// 清除字符串开头及结尾的空格
    while(s!=""&&s[0]==' ')s.erase(0,1);
    while(s!=""&&s[s.length()-1]==' ')s.erase(s.length()-1,1);
}

inline bool get_int(string s,LL&b){
    b=0;
    for(int i=0;i<s.length();++i)
        if(isdigit(s[i]))
            b=b*10+(s[i]^'0');
        else
            return 1;
    return 1;
}

vector<string>output;

inline bool chk_bad_no(){// 判断是否是 bad usage 或者 no such command
    if(output.empty())return 0;
    return output.size()==1&&(output[0]=="bad usage\n"||output[0]=="no such command\n");
}

inline void bad_usage(){
    output.clear();output.push_back("bad usage\n");
}

inline void no_such_command(){
    output.clear();output.push_back("no such command\n");
}

int Fid;// 文件编号

struct File{
    int Father;// 父文件夹编号
    bool dir;// 0: 文件  1: 文件夹
    bool hide;// 0: 显示  1: 隐藏
    string name;// 文件名
    map<string,int>son;// 子文件对应编号
    LL size;// 文件大小
    void clear(){// 清除文件内容
        dir=hide=0,name="";size=0;son.clear();Father=0;
    }
    inline int find(string s){
        if(!son.count(s))return -1;
        return son[s];
    }
}F[100005];

int nowDir;

struct data{// 用来存储 ls/find 命令需要输出的信息，方便排序
    string info;
    int id;
    LL size;
};

vector<data>out;

inline bool cmp1(const data&a,const data&b){
    return a.size==b.size?a.info<b.info:a.size<b.size;
}
inline bool cmp2(const data&a,const data&b){
    return a.size==b.size?a.info<b.info:a.size>b.size;
}
inline bool cmp3(const data&a,const data&b){
    return a.info<b.info;
}

inline void get_tag(vector<string>&cs,int&tag,string ch){// 查找参数
    tag=0;
    for(int i=0;i<cs.size();++i)
         if(cs[i]==ch){
             tag=1;
             return;
         }
}

inline bool check_filename(string s){// 判断一个文件名是否合法
    if(s==".")return 0;
    if(s=="")return 0;
    if(s.find("..")!=string::npos)return 0;
    if(s.length()>255)return 0;
    for(int i=0;i<s.length();++i){
        if(s[i]!='.'&&!isalpha(s[i])&&!isdigit(s[i]))return 0;
    }
    return 1;
}

inline string getPath(int id){// 提取文件/目录的绝对路径
    if(F[id].Father==-1)return F[id].name;
    return getPath(F[id].Father)+"/"+F[id].name;
}

inline string getinfo(int id){
    string ret=getPath(id)+" ";
    LL sz=F[id].size;
    if(sz==0)ret+="0";else{
        string t="";
        while(sz){
            t=(char)(sz%10+'0')+t;
            sz/=10;
        }
        ret+=t;
    }
    if(F[id].hide)ret+=" hidden";
    if(F[id].dir)ret+=" dir";
    return ret;
}

void findcmd(int nowdir,vector<data>&info,string&name,int r,int h){// find 命令递归实现部分
    if(F[nowdir].son.count(name)){
        int id=F[nowdir].son[name];
        if(h==1||F[id].hide==0)
            info.push_back((data){getPath(id),id,0});
    }else
    if(name=="")
    for(map<string,int>::iterator it=F[nowdir].son.begin();it!=F[nowdir].son.end();++it){
        int id=it->second;
        if(h==1||F[id].hide==0)
            info.push_back((data){getPath(id),id,0});
    }
    if(r)
    for(map<string,int>::iterator it=F[nowdir].son.begin();it!=F[nowdir].son.end();++it){
        int id=it->second;
        if(F[id].dir)findcmd(id,info,name,r,h);
    }
}

inline int findFile(string path){// 根据路径寻找文件
    erase_space(path);
    if(path=="")return nowDir;
    int now=nowDir;
    if(path[0]=='/')now=0;
    for(int i=0;i<path.size();++i)
        if(path[i]=='/')path[i]=' ';
    istringstream in(path);
    string name;
    while(in>>name){
        if(now==-1||F[now].dir==0)return -1;
        if(name==".")continue;
        if(name=="..")
            now=F[now].Father;
        else
            now=F[now].find(name);
    }
    return now;
}

inline int splitPath(string full,string&file){// 分离路径和文件名，返回值为路径编号
    if(full.find("/")==string::npos){
        file=full;
        return nowDir;
    }
    file="";
    while(full[full.length()-1]!='/')
        file=full[full.length()-1]+file,full.erase(full.length()-1,1);
    full.erase(full.length()-1,1);
    if(full=="")return 0;
    int ret=findFile(full);
    if(ret!=-1&&F[ret].dir)return ret;
    return -1;
}

void cmdStart(){// 多测不清空，爆零两行泪
    for(int i=0;i<=Fid;++i)
        F[i].clear();
    F[0].Father=-1;
    F[0].dir=1;
    nowDir=0;
    Fid=0;
}

void cd(vector<string>&args,vector<string>&cs){// cd 命令
    string cmd=args[0];
    erase_space(cmd);
    int f=findFile(cmd);
    if(f==-1||F[f].dir==0)
        output.push_back("path not found\n");
    else
        nowDir=f;
}

void pwd(){// pwd 命令
    string path=getPath(nowDir);
    if(path=="")path="/";
    output.push_back(path+"\n");
}

void mkdir(vector<string>&args,vector<string>&cs){// mkdir 命令，创建目录 (mkdir path [-h])
    string filename="";
    int h=0;
    get_tag(cs,h,"h");
    int f=splitPath(args[0],filename);
    if(f==-1){
        output.push_back("path not found\n");
        return;
    }
    if(!check_filename(filename)){
        bad_usage();
        return;
    }
    if(F[f].find(filename)!=-1){
        output.push_back("file or directory with the same name exists\n");
        return;
    }
    int id=++Fid;
    F[id].name=filename,F[id].dir=1,F[id].hide=h;
    F[id].size=0;F[id].Father=f;
    F[f].son[filename]=id;
}


void touch(vector<string>&args,vector<string>&cs,LL size){// touch 命令，创建文件 (touch filename [-size] [-h])
    int hide=0;
    if(size==inf)size=0;
    get_tag(cs,hide,"h");
    string filename="";
    int f=splitPath(args[0],filename);
    if(f==-1){
        output.push_back("path not found\n");
        return;
    }
    if(!check_filename(filename)){
        bad_usage();
        return;
    }
    if(F[f].find(filename)!=-1){
        int id=F[f].find(filename);
        if(F[id].dir==1)
            output.push_back("a directory with the same name exists\n");
        else
            F[id].size=size,F[id].hide=hide;
        return;
    }
    int id=++Fid;
    F[id].name=filename,F[id].dir=0,F[id].hide=hide;
    F[id].size=size;F[id].Father=f;
    F[f].son[filename]=id;
}

void find(vector<string>&args,vector<string>&cs){// find 命令，查找文件 (find filename [-r] [-h])
    int r=0,h=0;
    get_tag(cs,r,"r"),get_tag(cs,h,"h");
    string filename="";
    int f=splitPath(args[0],filename);
    if(f==-1||F[f].dir==0){
        output.push_back("path not found\n");
        return;
    }
    out.clear();
    findcmd(f,out,filename,r,h);
    if(out.size()==0)
        output.push_back("file not found\n");
    else{
        sort(out.begin(),out.end(),cmp3);
        for(int i=0;i<out.size();++i)
            output.push_back(getinfo(out[i].id)+"\n");
    }
}

void ls_find(int nowdir,int h,int r,int d,int f){// ls 命令递归实现部分
    for(map<string,int>::iterator it=F[nowdir].son.begin();it!=F[nowdir].son.end();++it){
        int id=it->second;
        if(F[id].dir){
            if(d||(!d&&!f)){
                if(F[id].hide==0||h)out.push_back((data){getPath(id),id,F[id].size});
            }
            if(r)
                ls_find(id,h,r,d,f);
        }else{
            if(f||(!d&&!f)){
                if(F[id].hide==0||h)out.push_back((data){getPath(id),id,F[id].size});
            }
        }
    }
}

void ls(vector<string>&args,vector<string>&cs){
    int h=0,r=0,ss=0,S=0,f=0,d=0;
    get_tag(cs,h,"h");get_tag(cs,r,"r");
    get_tag(cs,ss,"s");get_tag(cs,S,"S");
    get_tag(cs,f,"f");get_tag(cs,d,"d");
    int nowdir=args.size()?findFile(args[0]):nowDir;
    if(nowdir==-1||F[nowdir].dir==0){
        output.push_back("path not found\n");
        return;
    }
    out.clear();
    ls_find(nowdir,h,r,d,f);
    if(out.empty()||(f&&d))
        output.push_back("[empty]\n");
    else{
        sort(out.begin(),out.end(),(ss?cmp1:(S?cmp2:cmp3)));
        for(int i=0;i<out.size();++i)
            output.push_back(getinfo(out[i].id)+"\n");
    }
}

inline int splitCmd(string cmd,string&Command,vector<string>&s1,vector<string>&s2,LL&size){// 分离命令
    s1.clear(),s2.clear(),Command="";size=inf;
    erase_space(cmd);
    istringstream in(cmd);
    string sth;
    if(!(in>>sth))return 2;// 空命令返回
    Command=sth;
    while(in>>sth){
        if(sth[0]=='-'){// 可选参数
            sth.erase(0,1);
            if(isalpha(sth[0])){
                s2.push_back(sth);
            }
            else
                if(isdigit(sth[0]))
                    get_int(sth,size);
                else{
                    bad_usage();
                    return 1;
                }
        }else{// 必选参数
            s1.push_back(sth);
        }
    }
    return 0;// 正常返回
}

void runCommand(string cmd,vector<string>&args,vector<string>&cs,LL size){
    if(cmd=="")return;
    if(cmd=="cd"){
        if(args.size()!=1){
            bad_usage();return;
        }
        cd(args,cs);
    }else
    if(cmd=="mkdir"){
        if(args.size()!=1){
            bad_usage();return;
        }
        mkdir(args,cs);
    }else
    if(cmd=="touch"){
        if(args.size()!=1){
            bad_usage();return;
        }
        touch(args,cs,size);
    }else
    if(cmd=="find"){
        if(args.size()!=1){
            bad_usage();return;
        }
        find(args,cs);
    }else
    if(cmd=="ls"){
        if(args.size()>1){
            bad_usage();return;
        }
        ls(args,cs);
    }else
    if(cmd=="pwd"){
        if(!args.empty()){
            bad_usage();return;
        }
        pwd();
    }else
    if(cmd=="exit"){
        if(!args.empty()){
            bad_usage();return;
        }
        cmdStart();
    }else
    if(cmd=="grep")bad_usage();
    else no_such_command();
}

inline int runGrep(string cmd,LL size){
    erase_space(cmd);
    if(cmd.size()<2||cmd[0]!='"'||cmd[cmd.length()-1]!='"'){bad_usage();return 1;}
    cmd.erase(0,1),cmd.erase(cmd.length()-1,1);
    vector<string>text=output;
    output.clear();
    for(int i=0;i<text.size();++i){
        if(text[i].find(cmd)!=string::npos)
            output.push_back(text[i]);
    }
    return 0;
}

int main(){
    string cmd;
    cmdStart();
    while(getline(cin,cmd)){
        LL size=0;
        string order,nw="";
        vector<string>args,cs;
        vector<string>avx;// 每条通过管道分割的指令
        output.clear();
        int flag=0;
        while(cmd!=""){
            if(cmd[0]=='|'&&!flag)avx.push_back(nw),nw="";
            else
                nw+=cmd[0];
            if(cmd[0]=='"')flag^=1;
            cmd.erase(0,1);
        }
        avx.push_back(nw);
        if(splitCmd(avx[0],order,args,cs,size)==1)bad_usage();else
            runCommand(order,args,cs,size);
        for(int i=1;i<avx.size();++i){
            istringstream in(avx[i]);
            if(!(in>>order)||order!="grep"){bad_usage();break;}
            string s;
            getline(in,s);
            if(runGrep(s,size))break;
        }
        for(int i=0;i<output.size();++i)
            cout<<output[i];
    }
    return 0;
}
Powered by Hexo
Theme - Material