import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
*
* <p>Problem #122 - Trees on the level</p>
*
* Methode: Level order <br />
* Status : Accepted <br />
* Runtime: 0.200 <br />
* @author Mariya Vlaseva
*/
public class Main {
/** regular
expression used to split the input into parts (whitespace) **/
private static final
String INPUT_NODE_SEPARATOR = "\\s+";
/** regular
expression used to match empty parentheses () **/
private static final
String END_OF_TREE_MATCHER = "\\s*\\(\\)\\s*";
/** regular
expression used to remove parentheses and possible whitespace from the
input **/
private static final
String PARENTHESES_AND_WHITESPACE_REMOVAL = "\\)|\\(|\\s+";
/** regular
expression used to verify the right node syntax (number, position) **/
private static final
String NODE_SYNTAX_MATCHER = "\\s*\\(\\d+,[L|R]*\\)\\s*";
/** not completely
specified tree program output **/
private static final
String NOT_COMPLETE = "not complete";
/**
* @param args
* @throws
IOException
*/
public static void
main(String[] args) throws IOException {
BufferedReader
console = new BufferedReader(new InputStreamReader(System.in));
String line;
START:
while((line =
console.readLine()) != null) {
List<InputNode>
inputNodes
= new ArrayList<InputNode>();
while(true) {
boolean ready =
false;
String[] parts =
line.split(INPUT_NODE_SEPARATOR);
for(String n :
parts) {
if(n.matches(END_OF_TREE_MATCHER))
{
ready = true; break; }
if(!n.matches(NODE_SYNTAX_MATCHER))
{
System.out.println(NOT_COMPLETE);
continue START;
}
InputNode iNode =
new InputNode(n);
for(InputNode i :
inputNodes) {
if(i.equals(iNode)) {
System.out.println(NOT_COMPLETE);
continue START;
}
}
inputNodes.add(iNode);
}
if(ready) { break; }
line =
console.readLine();
}
Node root =
constructTree(inputNodes);
printTree(levelOrder(root),
"
", inputNodes.size());
}
}
private static Node
constructTree(List<InputNode> inputNodes) {
Node root = new
Node();
root.setRoot(true);
for(InputNode
inputNode : inputNodes) {
findNodePosition(root,
inputNode.getValue(),
inputNode.getPosition());
}
return root;
}
private static void
findNodePosition(Node root, Integer value, String currentPos) {
if(currentPos.equals(""))
{
root.setValue(value);
return;
}
char currDirection =
currentPos.charAt(0);
currentPos =
currentPos.substring(1);
Node node = null;
switch
(currDirection) {
case 'L' : {
node =
root.getLeft();
if(node == null) {
node = new Node();
root.setLeft(node);
}
findNodePosition(node,
value,
currentPos);
break;
}
case 'R' : {
node =
root.getRight();
if(node == null) {
node = new Node();
root.setRight(node);
}
findNodePosition(node,
value,
currentPos);
break;
}
}
}
private static
List<Integer> levelOrder(Node root) {
List<Integer>
output = new ArrayList<Integer>();
Queue<Node>
queue = new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty())
{
Node node =
queue.poll();
output.add(node.getValue());
Node l =
node.getLeft();
if(l != null) {
queue.add(l);
}
Node r =
node.getRight();
if(r != null) {
queue.add(r);
}
}
return output;
}
private static
<E> void printTree(List<E> values, String deliminator, int
originalSize) {
StringBuilder sb =
new StringBuilder();
String
delim = "";
int
count = 0;
for (E
value : values) {
if(value == null) {
break;
}
sb.append(delim).append(value);
delim = deliminator;
count++;
}
if(count != originalSize) {
System.out.println(NOT_COMPLETE);
} else
{
System.out.println(sb.toString());
}
}
public static class
InputNode {
private final
Integer value;
private final String
position;
public
InputNode(String input) {
input =
input.replaceAll(PARENTHESES_AND_WHITESPACE_REMOVAL, "");
String[] parts =
input.split(",");
value = new
Integer(parts[0]);
if(parts.length ==
1) {
position = "";
} else {
position = parts[1];
}
}
public Integer
getValue() {
return value;
}
public String
getPosition() {
return position;
}
@Override
public boolean
equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() !=
obj.getClass())
return false;
InputNode other =
(InputNode) obj;
if(!other.value.equals(value))
{
return false;
}
if(!other.position.equals(position))
return false;
return true;
}
@Override
public String
toString() {
return "(" + value +
"," + position + ")";
}
}
public static class
Node {
private Integer
value;
private boolean root;
private Node left;
private Node right;
public Node() {
this(null, null,
null, false);
}
public Node(Integer
value) {
this(null, null,
value, false);
}
public Node(Node
left, Node right, Integer value) {
this(left, right,
value, false);
}
public Node(Node
left, Node right, Integer value, boolean root) {
this.left = left;
this.value = value;
this.right = right;
this.root = root;
}
public boolean
isRoot() {
return root;
}
public void
setRoot(boolean root) {
this.root = root;
}
public Node
getLeft() {
return left;
}
public void
setLeft(Node left) {
this.left = left;
}
public Node
getRight() {
return right;
}
public void
setRight(Node right) {
this.right = right;
}
public void
setValue(Integer value) {
this.value = value;
}
public Integer
getValue() {
return this.value;
}
@Override
public String
toString() {
return
this.value.toString();
}
}
}