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 rightNodes
-node (node.left node.right)
- A
Node
which has an empty leftNode
-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
andtree3.txt
) are undersrc/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
Token
s is pretty bad.