fork download
copy 
  1. import java.util.ArrayList;
  2.  
  3. public class Main
  4. {
  5.    static class Node
  6.    {
  7.       boolean bracket;
  8.       ArrayList<Node> children;
  9.       String s;
  10.       Node next;
  11.  
  12.       Node(String str)
  13.       {
  14.          bracket = false;
  15.          children = new ArrayList<Node>();
  16.          s = str;
  17.          next = null;
  18.       }
  19.  
  20.       void addChild(Node child)
  21.       {
  22.          children.add(child);
  23.       }
  24.    }
  25.  
  26.    public static void main(String[] args)
  27.    {
  28.       String str = "a((f|c|e)h|a)d";
  29.       Node root = createTree(str);
  30.       printTree(root, "");
  31.    }
  32.  
  33.    static Node createTree(String s)
  34.    {
  35.       s = s.replaceAll("(\\(|\\||\\))(\\(|\\||\\))", "$1.$2");
  36.       char[] str = s.toCharArray();
  37.       java.util.Stack<Node> stack = new java.util.Stack<Node>();
  38.       Node root = new Node("");
  39.       stack.push(root); // start node
  40.       boolean justFinishedBrackets = false;
  41.       for (char c: str)
  42.       {
  43.          if (c == '(')
  44.          {
  45.             stack.peek().next = new Node("Y"); // node after brackets
  46.             stack.peek().bracket = true; // node before brackets
  47.          }
  48.          else if (c == '|' || c == ')')
  49.          {
  50.             Node last = stack.peek(); // for (ab|cd)e, remember b / d so we can add child e to it
  51.             while (!stack.peek().bracket) // while not node before brackets
  52.                stack.pop();
  53.             last.addChild(stack.peek().next); // for (b|c)d, add d as child to b / c
  54.          }
  55.          else
  56.          {
  57.             if (justFinishedBrackets)
  58.             {
  59.                Node next = stack.pop().next;
  60.                next.s = "" + c;
  61.                stack.push(next);
  62.             }
  63.             else
  64.             {
  65.                Node n = new Node(""+c);
  66.                stack.peek().addChild(n);
  67.                stack.push(n);
  68.             }
  69.          }
  70.          justFinishedBrackets = (c == ')');
  71.       }
  72.       return root;
  73.    }
  74.  
  75.    static void printTree(Node root, String prefix)
  76.    {
  77.       prefix = prefix.replaceAll("\\.", "");
  78.       for (Node child: root.children)
  79.          printTree(child, prefix + root.s);
  80.       if (root.children.isEmpty())
  81.          System.out.println(prefix + root.s);
  82.    }
  83. }
  84.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
afhd
achd
aehd
aad
https://ideone.com/fHeFJf
language:
Java (12.0.1)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!