ACM 题目解答:FILE MAPPING

Description

It is often helpful for computer users to see a visual representation of the file structure on their computers. The “explorer” in Microsoft Windows is an example of such a system. Before the days of graphical user interfaces, however, such visual representations were not possible. The best that could be done was to show a static “map”of directories and files, using indentation as a guide to directory contents. For example:

ROOT
|	DIR1
|       File1
|	File2
|	File3
|	DIR2
|	DIR3
|	File1
File1
File2

This shows that the root directory contains two files and three subdirectories. The first subdirectory contains 3 files, the second is empty and the third contains one file.

Input

Write a program that reads a series of data sets representing a computer file structure. A data set ends with a line containing a single *, and the end of valid data is denoted by a line containing a single #. The data set contains a series of file and directory names. (The root directory is assumed to be the starting point.) The end of a directory is denoted by a ‘]’ Directory names begin with a lower case ‘d’ and file names begin with a lower case ‘f’ File names may or may not have an extension (such as fmyfile.dat or fmyfile). File and directory names may not contain spaces.
Output

Note that the contents of any directory should list any subdirectories first, followed by files, if any. All files should be in alphabetical order within each directory. Note that each data set output is marked by the label “DATA SET x:” where x denotes the number of the set, beginning at 1. Note also the blank line between the output data sets. Each level of indentation should show a ‘|’ followed by 5 spaces.
Sample Input

file1
file2
dir3
dir2
file1
file2
]
]
file4
dir1
]
file3
*
file2
file1
*
#

Sample Output

DATA SET 1:
ROOT
|     dir3
|     |     dir2
|     |     file1
|     |     file2
|     dir1
file1
file2
file3
file4

DATA SET 2:
ROOT
file1
file2
import java.util.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main {
    
    public static void main(String[] args) throws java.lang.Exception {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        List<Node> nodes = new ArrayList<Node>();
        Node root = null;
        List<Node> dirCursor = new LinkedList<Node>();
        int cursor = -1;
        while (true) {
            String line = br.readLine();
            if ("#".equals(line)) {
                break;
            }
            if ("*".equals(line)) {
                root = null;
                cursor = -1;
                dirCursor.clear();
                continue;
            }
            if (root == null) {
                root = new Node();
                root.name = "ROOT";
                nodes.add(root);
                dirCursor.add(root);
                cursor++;
            }
            if (line.startsWith("f")) {
                dirCursor.get(cursor).fileList.add(line);
            } else if (line.startsWith("d")) {
                Node node = new Node();
                node.name = line;
                dirCursor.get(cursor).dirList.add(node);
                cursor++;
                if (cursor >= dirCursor.size()) {
                    dirCursor.add(node);
                } else {
                    dirCursor.set(cursor, node);
                }

            } else if (line.startsWith("]")) {
                cursor--;
            }
        }

        for (int i = 1; i <= nodes.size(); i++) {
            if (i != 1) {
                System.out.println();
            }
            System.out.println("DATA SET " + i + ":");
            printDir(nodes.get(i - 1), 0);
        }
    }
    
    public static void printDir(Node node, int depth) {
        for (int i = 0; i < depth; i++) {
            System.out.print("|     ");
        }
        System.out.println(node.name);
        if (!node.dirList.isEmpty()) {
            for (Node n : node.dirList) {
                printDir(n, depth + 1);
            }
        }
        Collections.sort(node.fileList);
        for (String s: node.fileList) {
            for (int i = 0; i < depth; i++) {
                System.out.print("|     ");
            }
            System.out.println(s);    
        }
        
    }
}


class Node {
    public String name;
    public List<String> fileList = new ArrayList<String>();
    public List<Node> dirList = new ArrayList<Node>();
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注