1
\$\begingroup\$

I have a tree in a file which looks like this:

(1 (2 (3 (10 11) 15) 4 (5 (() 13) 6)))

Here, a Node and its children are written like this:

  • A Node with its left are right Nodes - node (node.left node.right)
  • A Node which has an empty left Node - node (() node.right)
  • The Root Node is special and is written as (rootNode (rootNode.left rootNode.right)

A tree is derived with this BNF form:

S -> (E)
E -> E(EE)|()|<numbers>

Thus, () and (()) are valid trees but (()()) is not.


Now, I want to create a Tree with any such inputs. I also wanted to be able to create a Tree<String> which might have inputs like:

(a (b (also (some ()) there) c))

etc.

Here is my Tree:

package org.yadavvi.util;

import java.util.ArrayList;
import java.util.List;

public class Tree<T> {

    public Node<T> root;

    public Tree(Node<T> node) {
        root = node;
    }

    public static <T> int maxDepthOfTree(Tree<T> tree) {
        if (tree == null) return -1;
        if (tree.root == null) return 0;
        int depth = 0;

        List<Node<T>> nodesAtLevel = new ArrayList<>();
        List<Node<T>> nodes = new ArrayList<>();

        nodesAtLevel.add(tree.root);
        nodes.addAll(nodesAtLevel);
        nodesAtLevel.clear();

        while (!nodes.isEmpty()) {
            nodesAtLevel.clear();
            depth++;

            for (Node<T> node : nodes) {
                if (node.left != null) nodesAtLevel.add(node.left);
                if (node.right != null) nodesAtLevel.add(node.right);
            }

            nodes.clear();
            nodes.addAll(nodesAtLevel);
        }
        return depth;
    }

    public static class Node<T> {
        public T value;
        public Node<T> left;
        public Node<T> right;

        public Node(T value) {
            this.value = value;
            left = null;
            right = null;
        }

        @Override
        public boolean equals(Object obj) {
            return value.equals(obj);
        }

        @Override
        public int hashCode() {
            return value.hashCode();
        }
    }

}

This is the Utility class that I use to create the tree:

package org.yadavvi.util;

import org.yadavvi.util.Tree.Node;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Stack;

public class TreeUtil {

    public static <T> Tree<T> createTreeFromFile(String fileName) {
        try (BufferedReader inputStream = new BufferedReader(new FileReader(fileName))) {
            return createTreeFromString(inputStream.readLine());
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }

    private static <T> Tree<T> createTreeFromString(String s) {
        return new Tree<>(createTree(s));
    }

    private static <T> Node<T> createTree(String s) {
        return createTree(new Expression(s));
    }

    private static <T> Node<T> createTree(Expression expression) {
        Stack<Node<T>> nodeStack = new Stack<>();
        Stack<Token<T>> tokenStack = new Stack<>();

        Token<T> token = getNextToken(expression);

        while (token != null) {
            if (token instanceof OpenParenthesis) {
                tokenStack.push(token);
            } else if (token instanceof Element) {
                nodeStack.push(getNodeFromElement((Element) token));
            } else if (token instanceof EmptyElement) {
                nodeStack.push(null);
            } else if (token instanceof CloseParenthesis) {
                if (nodeStack.size() == 1) {
                    if (tokenStack.size() != 1) {
                        throw new IllegalArgumentException("When a CloseParenthesis is encountered " +
                                "and there is only one Node viz. the root Node in the nodeStack, " +
                                "there should be only 1 OpenParenthesis in the tokenStack.");
                    }
                    tokenStack.pop();
                    return nodeStack.pop();
                }

                tokenStack.pop();
                Node<T> right = nodeStack.pop();
                Node<T> left = nodeStack.pop();
                Node<T> node = nodeStack.pop();
                node.left = left;
                node.right = right;
                nodeStack.push(node);
            }

            token = getNextToken(expression);
        }

        return null;
    }

    private static <T> Node<T> getNodeFromElement(Element<T> token) {
        return new Node<>(token.getValue());
    }

    private static <T> Token<T> getNextToken(Expression expression) {
        String s = expression.s;
        Token<T> token = null;
        int i = 0;
        while (i < s.length() && s.charAt(i) == ' ') i++;

        if (i != s.length()) {
            if (s.charAt(i) == '(') {
                while (s.charAt(i) == ' ' && i < s.length()) i++;
                if (s.charAt(i + 1) == ')') {
                    token = new EmptyElement<T>();
                    i++;
                } else {
                    token = new OpenParenthesis<T>();
                }

                i++;
            } else if (s.charAt(i) == ')') {
                i++;
                token = new CloseParenthesis<>();
            } else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                int value = 0;
                while (s.charAt(i) >= '0' && s.charAt(i) <= '9' && i < s.length()) {
                    value = value * 10 + s.charAt(i) - '0';
                    i++;
                }
                token = new Element<>(value);
            } else {
                token = new Element<>("Trees with string instead of integers should be resolved here.");
            }
        }
        expression.s = s.substring(i);

        return token;
    }

    private static class Expression {
        String s;

        Expression(String s) {
            this.s = s;
        }
    }

    private static abstract class Token<T> { }

    private static class OpenParenthesis<T> extends Token { }

    private static class CloseParenthesis<T> extends Token { }

    private static class EmptyElement<T> extends Token { }

    private static class Element<T> extends Token {
        T value;

        Element(T value) {
            this.value = value;
        }

        public T getValue() {
            return value;
        }
    }

}

My input files look like this:

  • tree1.txt - (1 (2 (3 (10 11) 15) 4 (5 (() 13) 6)))
  • tree2.txt - (1 (2 (3 (10 11) 15) 4 (5 6)))
  • tree3.txt - (1(()()))

Project Structure

I have created a gradle project. The project structure is as follows -

  • The source files are under src/main/java/org/yadavvi/util
  • The test files are under src/test/java/org/yadavvi/util
  • the input resources (files tree1.txt, tree2.txt and tree3.txt) are under src/test/resources/org/yadavvi/util

The test file ReadTreeTest.java (which is under src/test/java/org/yadavvi/util) looks like this -

package org.yadavvi.util;

import junitparams.JUnitParamsRunner;
import junitparams.Parameters;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;

import static org.yadavvi.util.TreeUtil.createTreeFromFile;

@RunWith(JUnitParamsRunner.class)
public class ReadTreeTest {

    public Object[] filesForTrees() {
        return new Object[]{
                new Object[]{"tree1.txt"},
                new Object[]{"tree2.txt"},
                new Object[]{"tree3.txt"}
        };
    }

    @Before
    public void setUp() throws Exception {

    }

    @Test
    @Parameters(method = "filesForTrees")
    public void createTreeTest(String resourceName) throws Exception {
         createTreeFromFile(fileName);
    }
}

The project gradle file - build.gradle - looks like this -

group 'org.yadavvi'
version '1.0-SNAPSHOT'

apply plugin: 'java'

sourceCompatibility = 1.8

repositories {
    mavenCentral()
}

dependencies {
    testCompile group: 'org.hamcrest', name: 'hamcrest-junit', version: '2.0.0.0'
    testCompile group: 'pl.pragmatists', name: 'JUnitParams', version: '1.0.6'
    testCompile group: 'junit', name: 'junit', version: '4.12'
}

Things I want feedbacks about:

  • I have used createTree() using generics, however, I am getting a lot of typecast warnings.
  • The logic of getting Tokens is pretty bad.
\$\endgroup\$
  • \$\begingroup\$ How do you run this? What's the entry point? \$\endgroup\$ – Tamas Rev May 11 '17 at 11:56
  • \$\begingroup\$ @TamasRev I have edited the question to add a details about running the project. \$\endgroup\$ – yadav_vi May 11 '17 at 12:15
2
\$\begingroup\$

Most of the typecast warnings can be eliminated if you specify the Token -s type at the subclasses too:

private static class OpenParenthesis<T> extends Token<T> { }

So the compiler knows that an OpenParenthesis<String> is a subclass of Token<String>. Also, an OpenParenthesis<String> is not a subclass of Token<Integer>.

You can get rid of the other typecast warning at line 39 if you specify the the generic type of element:

nodeStack.push(getNodeFromElement((Element<T>) token));

There were two more warnings in getNextToken. The warning basically said that you could use the diamond syntax for the new EmptyElement and OpenParentheses. I.e. replace this:

token = new EmptyElement<T>();
...
token = new OpenParenthesis<T>();

with this:

token = new EmptyElement<>();
...
token = new OpenParenthesis<>();

Now we don't have too many warnings. However, there are two compile-time errors:

            int value = 0;
            // here is a compile-time error
            token = new Element<>(value);
        } else {
            // here is a compile-time error too
            token = new Element<>("Trees with string instead of integers should be resolved here.");

The problem is that you want to create an Element<T> either from Integer or from String. This is impossible because they don't belong to the same object tree - other than the general Object itself.

So you can do some casting and hope everything will be allright:

    Integer value = 0; // Integer for casting
    //
    token = new Element<>((T) value); // casting the value
} else {
    token = new Element<>((T) "Trees with string instead of integers should be resolved here."); // casting the value
}

However, I'd rather use String-s only and cast the values at a later step.

Other suggestions:

Some classes, like OpenParenthesis or EmptyElement do nothing. I suggest to use an enum instead.

Try to use less static methods.

The createTree method returns null no matter what. I'd move the stack-to-tree logic into a separate method and I'd invoke that here.

\$\endgroup\$
  • \$\begingroup\$ Integer value = 0; token = new Element<T>((T) value); gives compilation error even after making private static class Element<T> extends Token<T> instead of private static class Element<T> extends Token. \$\endgroup\$ – yadav_vi May 11 '17 at 12:29
  • \$\begingroup\$ On the one hand, it's my bad. It's enough to write new Element<>((T) value);. On the other hand it does not give compilation error. It gives a warning: Unchecked cast from Integer to T. Did you change the signature of getNextToken() ? \$\endgroup\$ – Tamas Rev May 11 '17 at 12:34
  • \$\begingroup\$ It worked with using Integer value; instead of int value, I'm sorry. Can you explain what the difference between private static class Element<T> extends Token<T> and private static class Element<T> extends Token is ? \$\endgroup\$ – yadav_vi May 11 '17 at 12:39
  • \$\begingroup\$ If you write private static class Element<T> extends Token<T> then you make sure that the Element class uses the same type as Token does. I.e. Element<Integer> element = new Element<>(); will set the type token of Element and Token to Integer. On the other hand, if you write private static class Element<T> extends Token<T>, then Element<Integer> element = new Element<>(); will specify the Element type as Integer, however, Token -s type remains unspecified. \$\endgroup\$ – Tamas Rev May 11 '17 at 12:42
  • \$\begingroup\$ Did you mean - "On the other hand, if you write private static class Element<T> extends Token, then Element<Integer> element = new Element<>(); will specify the Element type as Integer, however, Token -s type remains unspecified." instead of what you've written? \$\endgroup\$ – yadav_vi May 11 '17 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.