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个命令，具体如下表所示。 | 用法 | 描述 | | ------------------------------------------- | ------------------------------------------------------------ | | **cd** path | 改变当前目录。path 可以是相对路径，也可以是绝对路径。如果目录不存在或名称不合法，输出 `path not found` 。 | | **touch** filename [-size] [-h] | 修改文件。filename 的最后一部分应该是合法的文件名，否则输出 `bad usage` (详见后)。文件名之前的部分应当是文件系统中存在的目录，否则输出 `path not found` 。在正常情况下，同名文件(如果有的话)应当先被删除，然后新建文件。文件的大小由 -size 参数给出(默认为0),参数-h表示创建隐藏文件。如果存在同名的目录，输出 `a dretory with the same name exists` 。用户不会指定多个 -size 参数。 | | **mkdir** path [-h] | 创建目录。path 的最后一部分应该是 合法的文件名，否则输出 `bad usage` (见后)。文件名之前的部分应当是文件系统中存在的目录，否则输出 `path not found`。参数 -h 表示创建隐藏目录。如果存在一个同名目录或文件，输出 `file or directory with the same name exists` 。 | | **find** filename [-r] [-h] | 查找目录或文件。filename 的最后一部分 应该是合法的文件名(否则按找不到处理)，表示查找的目录或者文件的名称，这之前的部分应当是文件系统中存在的目录，否则输出 `path not found`。-r 参数表示当前目录下的所有子目录也要查找。默认情况下，find 命令在显示结果时会忽略掉隐藏文件（但会在隐藏目录中进行查找）， 如果加了 -h 参数，则会连隐藏文件一起显示。如果没有一个需要输出的文件，输出 `file not found` 。否则对于找到的每个文件，输出单独的一行，依次包含带绝对路径的文件名、文件大小，以及 hidden （如果有隐藏属性）、 dir （如果是目录）。这些文件应当按照带绝对路径的文件名的字典序从小到大输出。 | | **ls** [path] [-h] [-r] [-s] [-S] [-f] [-d] | 没有参数的情况下，Is 命令列出当前目录的所有非隐藏文件（格式同find）。如果没有一个需要输出的内容，输出 `[empty]`。如果path是文件系统中存在的目录，则列出该目录（而非当前目录）中的文件。如果指定了 path 參数但 path 不是一个合法的路径，则输出 `path not found` 。 -h 表示要列出隐藏文件(默认不显示)，-r 表示递归列出所有子目录的文件（即使未指定 -h 也需要进入隐藏目录递归），-s 表示按照文件大小的非降序排列（文件大小相同的情况仍按照带绝对路径的文件名的字典序排列），-S 表示按照文件大小的非升序排列（如文件大小相同则参见 -s），-d 表示只列出目录，-f 表示只列出非目录。用户不会同时指定 -s 和 -S 。 | | **pwd** | 输出当前目录的绝对路径 | | **exit** | 推出 bash | | **grep** "string" | 本题中，grep 只能通过管道的形式调用，即 command1 \| grep "string" ，表示先执行 command1，然后在命令输出结果中搜索字符串 “string” ，按照原顺序输出所有包含这个字符串的行。比如，如果前一个命令的输出是 `path not found` ，那么 grep "ot fou" 就应该也输出 `path not found` 。用户输入的 string 参数保证在一对引号内，且内部不含引号，也没有转义符。 | 命令行包含一条或多条命令，用管道符号 `|` 隔开（管道符号的前后不一定有空格）。第一条命令必须是除了 grep 之外的上述命令之一，而剩下的命令必须是grep。如果违反上述规定，应输出 `bad usage`，并且不执行任何命令。输入不会在除了 grep 之外的其他命令中使用引号。（原题未写，但书中是这么说的）如果上一条命令输出了 `bad usage` 或者 `no such command` ，则不再执行后面的命令。 命令和参数、参数和参数之间用一个或多个空格隔开。 每个命令的必选参数（如果有的话）不一定是第一个参数，可选参数可能在必选参数之前，且以任意顺序出现。如果用户忽略了必选参数，或传入了过多必选参数，应输出 `bad usage` 。但忽略传入的无效可选参数（如 `mkdir a -h -h -h -h -abababab` 等价于 `mkdir a -h`） ~~（原文题意描述非常不清晰，不保证绝对正确）~~ ### 输入格式 输入包含多组数据，每组数据对应一次独立的 BASH 会话。数据的每行为一行命令（长度不超过 2048 个字符）。命令的参数之间可以有任意数量的空白字符。每次会话的最后一条命令保证为exit。输入结束标志为文件结束符（EOF）。假定每次会话开始时，文件系统为空，当前目录为根目录。 ### 输出格式 对于每个会话，输出相应的回答。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1907 [PDF](https://uva.onlinejudge.org/external/109/p10966.pdf) 



pwd
cd acm
mkdir ./acm
ls ./acm
cd acm
pwd
touch acm -h -1000
cd ..
cd /
grep
ls -r -s
ls -r -h
find acm -h -r | grep "1000"
exit

/
path not found
[empty]
/acm
bad usage
/acm 0 dir
/acm 0 dir
/acm/acm 1000 hidden
/acm/acm 1000 hidden