1.

/**
* ACM
* UVa Status: accepted
* Run Time: 0.530
* Category: Graphs
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
import java.io.*;
import java.util.*;

public class Main {

private static class Tree {

// saves context
private int currentLevel = 0, maxLevel = -1;
// saves the nodes for each level
private List<List<Character>> level = new ArrayList<List<Character>>();


public void insert(char c)
{
if(currentLevel > maxLevel)
{
level.add(new ArrayList<Character>());
maxLevel = currentLevel;
}

level.get(currentLevel).add(c);

// find next level
if(Character.isUpperCase(c))
currentLevel++;
else
while(level.get(currentLevel).size() % 2 == 0 )
currentLevel--;
}

public String out()
{
StringBuffer buffer = new StringBuffer();

Collections.reverse(level);
for(List <Character> list: level)
for(Character c: list)
buffer.append(c);

return buffer.toString();
}
}


public static void main(String ...args)
{
Scanner sc = new Scanner(System.in);
int cases = sc.nextInt();
String input;

for(int i = 0; i < cases; i++)
{
Tree tree = new Tree();
input = new StringBuffer(sc.next()).reverse().toString();
for(int c = 0; c < input.length(); c++)
tree.insert(input.charAt(c));

System.out.println(tree.out());
}
}

}



2.

/**
* ACM
* UVa Status: accepted

* Category: Graphs
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/

import java.io.*;
import java.util.*;

public class Main {

private static class Node {

public char value;
public Node left,right,parent;

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

private static class Tree {

private Node root = null, current;
private int currentLevel, maxLevel;
private List<List<Character>> level = new ArrayList<List<Character>>();

public void insert(Node n)
{
if(root == null)
{
root = n;
current = root;
currentLevel = 1;
level.add(new ArrayList<Character>());
level.add(new ArrayList<Character>());
level.get(0).add(n.value);
return;
}

// add node
if(current.left == null)
current.left = n;
else
current.right = n;
n.parent = current;
level.get(currentLevel).add(n.value);

// search for next candidate
if(Character.isUpperCase(n.value))
{
current = n;
currentLevel++;
if(currentLevel > maxLevel)
{
level.add(new ArrayList<Character>());
maxLevel = currentLevel;
}
}
else
while(current.parent != null && current.right != null)
{
current = current.parent;
currentLevel--;
}
}

public String out()
{
StringBuffer buffer = new StringBuffer();

Collections.reverse(level);
for(List <Character> list: level)
for(Character c: list)
buffer.append(c);

return buffer.toString();
}
}


public static void main(String ...args)
{
Scanner sc = new Scanner(System.in);
int cases = sc.nextInt();
String input;

for(int i = 0; i < cases; i++)
{
Tree tree = new Tree();
input = new StringBuffer(sc.next()).reverse().toString();
for(int c = 0; c < input.length(); c++)
tree.insert(new Node(input.charAt(c)));

System.out.println(tree.out());
}
}

}