How to Build a Binary Tree from a String Expression-CodePudding

Given a String such as this one, (((!D!)B!)A((!F(!H!))C(!G!))) with no white space. How would you build a binary tree?

I am supposed to implement a constructor and build it with an inoder traversal. This String would output

Any help/tips would be very appreciated!!!

CodePudding user response：

Try this.

static Node parse(String input) {
    return new Object() {
        final int length = input.length();
        int index = 0;
        int ch = get();
        int get() { return ch = index < length ? input.charAt(index  ) : -1; }

        Node node() {
            if (ch == '!') {
                get();
                return null;
            } else if (ch == '(') {
                get();
                Node left = node();
                char data = (char)ch;
                get();
                Node right = node();
                if (ch != ')')
                    throw new RuntimeException("')' expected");
                get();
                return new Node(left, data, right);
            } else
                throw new RuntimeException("'!' or '(' expected");
        }

        Node parse() {
            Node node = node();
            if (ch != -1)
                throw new RuntimeException("extra string: "   input.substring(index - 1));
            return node;
        }
    }.parse();
}

And

public static void main(String[] args) {
    String input = "(((!D!)B!)A((!F(!H!))C(!G!)))";
    Node root = parse(input);
    System.out.println(root);
}

output:

Node[left=Node[left=Node[left=null, data=D, right=null], data=B, right=null], data=A, right=Node[left=Node[left=null, data=F, right=Node[left=null, data=H, right=null]], data=C, right=Node[left=null, data=G, right=null]]]

CodePudding user response：

you can parse using recursion:

public BinaryTree(String t) {
    this.root = parse(new StringReader(t));
}

private static Node parse(StringReader reader) {
    char c = (char)reader.read();
    if (c == '!')
        return null;
    if (c == '(') {
        Node left = parse(reader);
        char data = (char)reader.read();
        Node right = parse(reader);
        if (reader.read() != ')')
            throw new IllegalArgumentException();
        return new Node(left, data, right);
    }
    throw new IllegalArgumentException();
}