java - 如何使用递归构建嵌套链表？

Question

所以在类里面我们被要求读取一个文本文件。格式如下:

a b ( c d ( e f ) g ) h

我们需要构建一个嵌套链表，如下所示:

一个

b

.....c

...d

......e

......f

...g

小时

每个左括号表示向下移动一级，然后右括号表示向上移动一级。 因此，a 链接到 b，b 有一个到 c 的嵌套链接，c 链接到 d，d 有一个到 e 的嵌套链接，e 链接到 f，d 链接到 g，然后 b 链接到 h

我们正在使用修改后的 LLNode:

公共(public)类LLNode {

protected LLNode<T> link;
protected LLNode<T> nested;
protected T info;
public LLNode(T info) 
{
    this.info = info;
    link = null;
    nested = null;
}
public void setInfo(T info) 
{
    this.info = info;
}
public T getInfo() 
{
    return info;
}
public void setLink(LLNode<T> link) 
{
    this.link = link;
}
public LLNode<T> getLink() 
{
    return link;
}
public void setNested(LLNode<T> nested)
{
    this.nested = nested;
}
public LLNode<T> getNested()
{
    return nested;
}

}

我们需要使用递归来读取输入文件，为每个字母创建节点并相应地链接它们。我不知道如何递归地处理这个问题。非常感谢任何帮助。

Answer 1

我知道我不应该给你作业的答案，但我喜欢递归，所以我无法抗拒这个。在你提交代码之前，请花一些时间理解并可能修改代码。聪明的老师会通过 StackOverflow 进行搜索，特别是如果你提交的东西出奇的好:)

我必须向 LLNode 添加一个parent。除了父属性之外，您还可以在 NodeParser 类中使用 LLNode 列表，其中该列表跟踪最近的父亲、祖父等。

新的 LLNode:

public class LLNode<T> {

    protected LLNode<T> link;
    protected LLNode<T> nested;
    protected LLNode<T> parent; // New field
    protected T info;

    public LLNode(T info) {
        <old code>
        parent = null;
    }

    <old code>

    public void setParent(LLNode<T> parent) {
        this.parent = parent;
    }

    public LLNode<T> getParent() {
        return parent;
    }

}

然后是解析器(包括递归打印机!):

public class NodeParser {

private String str;

public static void main(String[] args) {
    new NodeParser();
}

public NodeParser() {
    this.str = "a b ( c d ( e f ) g ) h ( i j ( k ) l ) m n";
    LLNode<Character> topNode = new LLNode<>(null);
    parse(topNode, false);
    print("", topNode.getLink());
}

private synchronized void parse(LLNode<Character> node, boolean nested) {
    if (str.length() == 0) {
        return;
    }
    while (str.charAt(0) == ' ') {
        str = str.substring(1);
    }
    char c = str.charAt(0);
    str = str.substring(1);

    if (c == '(') {
        parse(node, true);
    } else if (c == ')') {
        parse(node.getParent(), false);
    } else if (c >= 'a' && c <= 'z') {
        LLNode<Character> nextNode = new LLNode<>(c);
        if (nested) {
            node.setNested(nextNode);
            nextNode.setParent(node);
        } else {
            node.setLink(nextNode);
            nextNode.setParent(node.getParent());
        }
        parse(nextNode, false);
    }
}

private void print(String indent, LLNode<Character> node) {
    if (node == null) {
        return;
    }
    System.out.println(indent + node.getInfo());
    print(indent + "  ", node.getNested());
    print(indent, node.getLink());
}

}