import java.util.ArrayList;
public class Main
{
static class Node
{
boolean bracket;
ArrayList<Node> children;
Node next;
{
bracket = false;
children = new ArrayList<Node>();
s = str;
next = null;
}
void addChild(Node child)
{
children.add(child);
}
}
public static void main
(String[] args
) {
String str
= "a((f|c|e)h|a)d"; Node root = createTree(str);
printTree(root, "");
}
static Node createTree
(String s
) {
s = s.replaceAll("(\\(|\\||\\))(\\(|\\||\\))", "$1.$2");
char[] str = s.toCharArray();
java.util.Stack<Node> stack = new java.util.Stack<Node>();
Node root = new Node("");
stack.push(root); // start node
boolean justFinishedBrackets = false;
for (char c: str)
{
if (c == '(')
{
stack.peek().next = new Node("Y"); // node after brackets
stack.peek().bracket = true; // node before brackets
}
else if (c == '|' || c == ')')
{
Node last = stack.peek(); // for (ab|cd)e, remember b / d so we can add child e to it
while (!stack.peek().bracket) // while not node before brackets
stack.pop();
last.addChild(stack.peek().next); // for (b|c)d, add d as child to b / c
}
else
{
if (justFinishedBrackets)
{
Node next = stack.pop().next;
next.s = "" + c;
stack.push(next);
}
else
{
Node n = new Node(""+c);
stack.peek().addChild(n);
stack.push(n);
}
}
justFinishedBrackets = (c == ')');
}
return root;
}
static void printTree
(Node root,
String prefix
) {
prefix = prefix.replaceAll("\\.", "");
for (Node child: root.children)
printTree(child, prefix + root.s);
if (root.children.isEmpty())
System.
out.
println(prefix
+ root.
s); }
}