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.       char[] str = "a(b(f|c|e)h|a)d".toCharArray();
  29.       Node root = createTree(str);
  30.       printTree(root, "");
  31.    }
  32.  
  33.    static Node createTree(char[] str)
  34.    {
  35.       java.util.Stack<Node> stack = new java.util.Stack<Node>();
  36.       Node root = new Node("");
  37.       stack.push(root); // start node
  38.       boolean justFinishedBrackets = false;
  39.       for (char c: str)
  40.       {
  41.          if (c == '(')
  42.          {
  43.             if (stack.peek().bracket) // account for (( or |(, insert empty node in between
  44.             {
  45.                Node n = new Node("");
  46.                stack.peek().addChild(n);
  47.                n.next = stack.peek().next;
  48.                stack.push(n);
  49.             }
  50.             else
  51.                stack.peek().next = new Node(""); // node after brackets
  52.             stack.peek().bracket = true; // node before brackets
  53.          }
  54.          else if (c == '|' || c == ')')
  55.          {
  56.             Node last = stack.peek(); // for (ab|cd)e, remember b / d so we can add child e to it
  57.             while (!stack.peek().bracket) // while not node before brackets
  58.                stack.pop();
  59.             if (!justFinishedBrackets) // account for ))
  60.                last.addChild(stack.peek().next); // for (b|c)d, add d as child to b / c
  61.          }
  62.          else
  63.          {
  64.             if (justFinishedBrackets)
  65.             {
  66.                Node next = stack.pop().next;
  67.                next.s = "" + c;
  68.                stack.push(next);
  69.             }
  70.             else
  71.             {
  72.                Node n = new Node(""+c);
  73.                stack.peek().addChild(n);
  74.                stack.push(n);
  75.             }
  76.          }
  77.          justFinishedBrackets = (c == ')');
  78.       }
  79.       return root;
  80.    }
  81.  
  82.    static void printTree(Node root, String prefix)
  83.    {
  84.       for (Node child: root.children)
  85.          printTree(child, prefix + root.s);
  86.       if (root.children.isEmpty())
  87.          System.out.println(prefix + root.s);
  88.    }
  89. }
  90.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
abfhd
abchd
abehd
aad
https://ideone.com/iqLtso
language:
Java (12.0.1)
created:
11 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!