Отображение списка строк в иерархическую структуру объектов

Это не проблема домашней работы. Эти вопросы были заданы одному из моих друзей в интервью.

У меня есть list строк, считанных из файла в качестве входных данных. Каждая строка имеет идентификатор, такой как (A, B, NN, C, DD) в начале строки. В зависимости от идентификатора мне нужно сопоставить список записей с одним объектом A, который содержит иерархическую структуру объектов.

Описание иерархии: Каждый A может иметь ноль или более типов B. Каждый идентификатор B может иметь ноль или более NN и C как дочерний. Аналогично, каждый сегмент C может иметь ноль или более NN и DD child. Абд каждый 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 

    }
}

Моя логика работает неправильно. Есть ли другой подход, который вы можете понять? Есть ли у вас какие-либо предложения/улучшения для моего пути?

Ответы

    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 + " ");
        }
    }
}

public final class Parser {
    private final static class Token { /* represents A1 etc. */ }
    public final static class Node implements Iterable<Node> {
        /* One Token + Node children, knows its parent */
    }

    private enum State { ExpectA, SeenA, SeenB, SeenC, SeenDD, }

    public Node parse(String text) {
        return parse(Token.parseStream(text));
    }

    private Node parse(Iterable<Token> tokens) {
        State currentState = State.ExpectA;
        Node current = null, root = null;
        while(there are tokens) {
            Token t = iterator.next();
            switch(currentState) {
                /* do stuff for all states */

                /* example snippet for SeenC */
                case SeenC:
                if(t.Prefix.equals("B")) {
                    current.PN.PN.AddChildNode(new Node(t, current.PN.PN));
                    currentState = State.SeenB;
                } else if(t.Prefix.equals("C")) {

            }
        }
        return root;
    }
}

// "B" ("NN" || C)*
private Node rule_2(TokenStream ts, Node parent) {
    // Literal "B"
    Node B = literal(ts, "B", parent);
    if(B == null) {
        // error
        return null;
    }

    while(true) {
        // check for "NN"
        Node nnLit = literal(ts, "NN", B);
        if(nnLit != null)
            B.AddChildNode(nnLit);

        // check for C
        Node c = rule_3(ts, parent);
        if(c != null)
            B.AddChildNode(c);

        // finished when both rules did not match anything
        if(nnLit == null && c == null)
            break;
    }

    return B;
}

A  ::= { B }
B  ::= { NN | C }
C  ::= { NN | DD }
DD ::= { NN }

-- We are using some standard libraries.
import Control.Applicative ((<$>), (<*>))
import Text.Parsec
import Data.Tree

-- This is EBNF-like description of what to do.
-- You can almost read it like a prose.
yourData = nodeA +>> eof

nodeA  = node "A"  nodeB
nodeB  = node "B" (nodeC  <|> nodeNN)
nodeC  = node "C" (nodeNN <|> nodeDD)
nodeDD = node "DD" nodeNN
nodeNN = (`Node` []) <$> nodeLabel "NN"

node lbl children
  = Node <$> nodeLabel lbl <*> many children

nodeLabel xx = (xx++)
  <$> (string xx >> many digit)
  +>> newline

-- And this is some auxiliary code.
f +>> g = f >>= \x -> g >> return x

main = do
  txt <- getContents
  case parse yourData "" txt of
    Left err  -> print err
    Right res -> putStrLn $ drawTree res

$ ./xxx < zz.txt 
A1
+- B1
|  +- NN1
|  +- NN2
|  `- C1
|     +- NN2
|     +- DD1
|     +- DD2
|     |  +- NN3
|     |  `- NN4
|     `- DD3
|        `- NN5
`- B2
   +- NN6
   +- C2
   |  +- DD4
   |  +- DD5
   |  |  +- NN7
   |  |  `- NN8
   |  `- DD6
   |     `- NN9
   `- C3
      +- DD7
      `- DD8

$ ./xxx
A1
B2
DD3
(line 3, column 1):
unexpected 'D'
expecting "B" or end of input