将字符串列表映射到对象的层次结构中

Question

这不是一个家庭作业问题.这个问题在面试中被问到了我的一位朋友.

我有list一行从文件中读取作为输入.每行在行首都有一个标识符,如(A,B,NN,C,DD).根据标识符,我需要将记录列表映射到A包含对象层次结构的单个对象.

层次结构描述: 每个都A可以有零个或多个B类型.每个B标识符可以有零个或多个NN并且C作为子标识符.类似地,每个C段可以具有零或更多NN和DD子.作为孩子,每个人都DD可以拥有零或更多NN.

映射类及其层次结构:

所有类都必须value保持String当前行的值.

**A - will have list of B**

    class A {
        List<B> bList;
        String value;

        public A(String value) {
            this.value = value;
        }

        public void addB(B b) {
            if (bList == null) {
                bList = new ArrayList<B>();
            }
            bList.add(b);
        }
    }


**B - will have list of NN and list of C**

    class B {
            List<C> cList;
            List<NN> nnList;
            String value;
                public B(String value) {
                this.value = value;
            }
                public void addNN(NN nn) {
                if (nnList == null) {
                    nnList = new ArrayList<NN>();
                }
                nnList.add(nn);
            }
                public void addC(C c) {
                if (cList == null) {
                    cList = new ArrayList<C>();
                }
                cList.add(c);
            }
        }

**C - will have list of DDs and NNs**

    class C {
            List<DD> ddList;
            List<NN> nnList;
            String value;
            public C(String value) {
                this.value = value;
            }
            public void addDD(DD dd) {
                if (ddList == null) {
                    ddList = new ArrayList<DD>();
                }
                ddList.add(dd);
            }
            public void addNN(NN nn) {
                if (nnList == null) {
                    nnList = new ArrayList<NN>();
                }
                nnList.add(nn);
            }
        }

**DD - will have list of NNs**

    class DD {
            String value;
            List<NN> nnList;
            public DD(String value) {
                this.value = value;
            }
            public void addNN(NN nn) {
                if (nnList == null) {
                    nnList = new ArrayList<NN>();
                }
                nnList.add(nn);
            }
        }

**NN- will hold the line only**

    class NN {
        String value;

        public NN(String value) {
            this.value = value;
        }
    }

我到目前为止做了什么:

该方法public A parse(List<String> lines)读取输入列表并返回该对象A.因为,可能有多个B,我已经创建了单独的方法'parseB来解析每个事件.

在parseB方法中,循环遍历 i = startIndex + 1 to i < lines.size()并检查行的开始."NN"的出现被添加到当前对象中B.如果在开始时检测到"C",则调用另一种方法parseC.当我们在开始时检测到"B"或"A"时,循环将中断.

在parseC_DD中使用了类似的逻辑.

public class GTTest {    
    public A parse(List<String> lines) {
        A a;
        for (int i = 0; i < lines.size(); i++) {
            String curLine = lines.get(i);
            if (curLine.startsWith("A")) { 
                a = new A(curLine);
                continue;
            }
            if (curLine.startsWith("B")) {
                i = parseB(lines, i); // returns index i to skip all the lines that are read inside parseB(...)
                continue;
            }
        }
        return a; // return mapped object
    }

    private int parseB(List<String> lines, int startIndex) {
        int i;
        B b = new B(lines.get(startIndex));
        for (i = startIndex + 1; i < lines.size(); i++) {
            String curLine = lines.get(i);
            if (curLine.startsWith("NN")) {
                b.addNN(new NN(curLine));
                continue;
            }
            if (curLine.startsWith("C")) {
                i = parseC(b, lines, i);
                continue;
            }
            a.addB(b);
            if (curLine.startsWith("B") || curLine.startsWith("A")) { //ending condition
                System.out.println("B A "+curLine);
                --i;
                break;
            }
        }
        return i; // return nextIndex to read
    }

    private int parseC(B b, List<String> lines, int startIndex) {

        int i;
        C c = new C(lines.get(startIndex));

        for (i = startIndex + 1; i < lines.size(); i++) {
            String curLine = lines.get(i);
            if (curLine.startsWith("NN")) {
                c.addNN(new NN(curLine));
                continue;
            }           

            if (curLine.startsWith("DD")) {
                i = parseC_DD(c, lines, i);
                continue;
            }

            b.addC(c);
            if (curLine.startsWith("C") || curLine.startsWith("A") || curLine.startsWith("B")) {
                System.out.println("C A B "+curLine);
                --i;
                break;
            }
        }
        return i;//return next index

    }

    private int parseC_DD(C c, List<String> lines, int startIndex) {
        int i;
        DD d = new DD(lines.get(startIndex));
        c.addDD(d);
        for (i = startIndex; i < lines.size(); i++) {
            String curLine = lines.get(i);
            if (curLine.startsWith("NN")) {
                d.addNN(new NN(curLine));
                continue;
            }
            if (curLine.startsWith("DD")) {
                d=new DD(curLine);
                continue;
            }       
            c.addDD(d);
            if (curLine.startsWith("NN") || curLine.startsWith("C") || curLine.startsWith("A") || curLine.startsWith("B")) {
                System.out.println("NN C A B "+curLine);
                --i;
                break;
            }

        }
        return i;//return next index

    }
public static void main(String[] args) {
        GTTest gt = new GTTest();
        List<String> list = new ArrayList<String>();
        list.add("A1");
        list.add("B1");
        list.add("NN1");
        list.add("NN2");
        list.add("C1");
        list.add("NNXX");
        list.add("DD1");
        list.add("DD2");
        list.add("NN3");
        list.add("NN4");
        list.add("DD3");
        list.add("NN5");
        list.add("B2");
        list.add("NN6");
        list.add("C2");
        list.add("DD4");
        list.add("DD5");
        list.add("NN7");
        list.add("NN8");
        list.add("DD6");
        list.add("NN7");
        list.add("C3");
        list.add("DD7");
        list.add("DD8");
        A a = gt.parse(list);
            //show values of a 

    }
}

我的逻辑不正常.您还可以找到其他方法吗？你对我的方式有什么建议/改进吗？

Answer 1

使用对象的层次结构:

    public interface Node {
        Node getParent();
        Node getLastChild();
        boolean addChild(Node n);
        void setValue(String value);
        Deque  getChildren();
    }

    private static abstract class NodeBase implements Node {
        ...     
        abstract boolean canInsert(Node n);    
        public String toString() {
            return value;
        }
        ...    
    }

    public static class A extends NodeBase {
        boolean canInsert(Node n) {
            return n instanceof B;
        }
    }
    public static class B extends NodeBase {
        boolean canInsert(Node n) {
            return n instanceof NN || n instanceof C;
        }
    }

    ...

    public static class NN extends NodeBase {
        boolean canInsert(Node n) {
            return false;
        }
    }

创建一个树类:

public class MyTree {

    Node root;
    Node lastInserted = null;

    public void insert(String label) {
        Node n = NodeFactory.create(label);

        if (lastInserted == null) {
            root = n;
            lastInserted = n;
            return;
        }
        Node current = lastInserted;
        while (!current.addChild(n)) {
            current = current.getParent();
            if (current == null) {
                throw new RuntimeException("Impossible to insert " + n);
            }
        }
        lastInserted = n;
    }
    ...
}

然后打印树:

public class MyTree {
    ...
    public static void main(String[] args) {
        List input;
        ...
        MyTree tree = new MyTree();
        for (String line : input) {
            tree.insert(line);
        }
        tree.print();
    }

    public void print() {
        printSubTree(root, "");
    }
    private static void printSubTree(Node root, String offset) {
        Deque  children = root.getChildren();
        Iterator i = children.descendingIterator();
        System.out.println(offset + root);
        while (i.hasNext()) {
            printSubTree(i.next(), offset + " ");
        }
    }
}