根据字符串输入构建树

Question

当提供字符串输入时，我一直在思考如何生成树。例如当我有以下形式的输入-

（1（2（3）（4））（5（6）（））

表示树将是这样-

            1
           / 
          2   5
         /   /
         3 4 6 ()

我可以从通常的tree.add（data）构建树，然后通过判断新节点是否大于或小于父节点来寻找要自添加的新节点。但我不知道如何实现如何以二进制数据结构的形式存储上面提到的字符串

以下是我迄今为止尝试过的

public class BinaryTree {
static Node root;
public static void levelorder(Node<?> n) {
    Queue<Node<?>> nodequeue = new LinkedList<Node<?>>();
    if (n != null)
        nodequeue.add(n);
    while (!nodequeue.isEmpty()) {
        Node<?> next = nodequeue.remove();
        System.out.print(next.data + " ");
        if (next.getLeft() != null) {
            nodequeue.add(next.getLeft());
        }
        if (next.getRight() != null) {
            nodequeue.add(next.getRight());
        }
    }
}
private static String[] breakString(String elements) {
    int indexOfOpenBracket = elements.indexOf("(");
    int indexOfLastBracket = elements.lastIndexOf(")");
    String removedPString = elements.substring(indexOfOpenBracket + 1,
            indexOfLastBracket);
    String[] breakRemovedPString = removedPString.split(" ");
    if (breakRemovedPString[1].contains("(")) {
        add(breakRemovedPString[0], breakRemovedPString[1], breakRemovedPString[2]);
    }
    return breakRemovedPString;
}
static void add(String parent, String leftString, String rightString) {
    Node<String> nodeToAdd = new Node<String>(parent);
    if (root == null) {
        root = nodeToAdd;
        root.left = new Node<String>(leftString);
        root.right = new Node<String>(rightString);
    } else {
    }
}
public static void main(final String[] args) {
    String treeString = "(1 (2) (3))";
    breakString(treeString);
    levelorder(root);
    System.out.println();
 }
}

请为这个问题提出一些实施建议。

Answer 1

这是一个经典的解析问题。最简单的方法可能是递归下降。以下是树语言的语法：

T -> ( number T T )
   | ( number )
   | ()

要将其转化为解析器，我们可以进行到LL（1）形式的形式转换，然后进行代码转换。我会让你仔细阅读并展示结果。

package treereader;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.io.Reader;
enum Token { LPAREN, RPAREN, NUMBER, EOF, ERROR };
class Scanner {
    final Reader in;
    final char [] buf = new char[1];
    final StringBuilder token = new StringBuilder();
    private static final char EOF_MARK = Character.MIN_VALUE;
    Scanner(Reader in) {
        this.in = in;
        read();
    }
    final void read() {
        try {
            if (in.read(buf) < 1) {
                buf[0] = EOF_MARK;
            }
        } catch (IOException ex) {
            System.err.println("i/o error");
            buf[0] = EOF_MARK;
        }
    }
    Token getNext() {
        while (Character.isWhitespace(buf[0])) {
            read();
        }
        if (Character.isDigit(buf[0])) {
            token.setLength(0);
            do {
                token.append(buf[0]);
                read();
            } while (Character.isDigit(buf[0]));
            return Token.NUMBER;
        }
        if (buf[0] == '(') {
            read();
            return Token.LPAREN;
        }
        if (buf[0] == ')') {
            read();
            return Token.RPAREN;
        }
        if (buf[0] == EOF_MARK) {
            return Token.EOF;
        }
        return Token.ERROR;
    }
    String getString() {
        return token.toString();
    }
}
class Node {
    public void print(PrintStream out) {
        out.print("()");
    }
}
class UnaryNode extends Node {
    int val;
    public UnaryNode(int val) {
        this.val = val;
    }
    @Override
    public void print(PrintStream out) {
        out.print("(" + val + ")");
   }
}
class BinaryNode extends Node {
    int val;
    Node left, right;
    public BinaryNode(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
    @Override
    public void print(PrintStream out) {
        out.print("(" + val + " ");
        left.print(out);
        out.print(' ');
        right.print(out);
        out.print(')');
    }
}
class Parser {
    final Scanner scanner;
    Token lookAhead;
    Parser(Reader in) {
        scanner = new Scanner(in);
        lookAhead = scanner.getNext();
    }
    void advance() {
        lookAhead = scanner.getNext();
    }
    void match(Token token) throws IOException {
        if (lookAhead == token) {
            advance();
        } else {
            throw new IOException("Expected " + token + ", found " + lookAhead);
        }
    }
    Node parse() throws IOException {
        Node tree;
        match(Token.LPAREN);
        if (lookAhead == Token.NUMBER) {
            int val = Integer.valueOf(scanner.getString());
            advance();
            if (lookAhead == Token.LPAREN) {
                Node left = parse();
                Node right = parse();
                tree = new BinaryNode(val, left, right);
            } else {
                tree = new UnaryNode(val);
            }
        } else {
            tree = new Node();
        }
        match(Token.RPAREN);
        return tree;
    }
}
public class TreeReader {
    public static void main(String[] args) {
        try {
            Parser parser = new Parser(new BufferedReader(new FileReader(new File(args[0]))));
            Node tree = parser.parse();
            tree.print(System.out);
        } catch (IOException ex) {
            System.err.println(ex.getMessage());
        }
    }    
}