Extract identifiers and corresponding brackets among overlapped brackets

Question

I have some files contained identifiers as below:

B#205918
A#273075
E#554065

Eg. sample of file1:

((((A#273075,A#273116),((A#224325,A#192952),A#243232)),(((E#7955,E#7165),E#6239),E#4530)),(((((E#3075,E#3702),B#251221),E#35128),B#243275),((B#198094,B#176280),B#273119)))

In this file, the identifiers only began from three alphabets (clusters); A/B/E. I would want to automate the extraction the identifiers that starts with A/B/E into separate files, where each file contain identifiers of those in the same cluster only.

The identifiers within the same bracket belongs to the same group. For example, ((B#198094,B#176280),B#273119)

B#198094 and B#196280 are within the same inner group, and together with B#273119, three of them are within the bigger group. That said, the brackets do matter during the extraction of the identifiers.

Basically what I can picture on the algorithm is to extract the identifiers and all the matching open & close brackets that enclosed them, when all the identifiers within the brackets start with those in same cluster (either A/B/E).

Expected output files:

cluster A:

((A#273075,A#273116),((A#224325,A#192952),A#243232))

cluster B:

((B#198094,B#176280),B#273119)

cluster E*:

(((E#7955,E#7165),E#6239),E#4530)
(E#3075,E#3702)

*It can be more than a single line in the extraction output files as there are possibilities for the identifiers of the same cluster not being placed in the same group (the outlier) -- It can be seen in the sample file that the two groups of identifiers in cluster E file were not enclosed by any common bracket, except the brackets that enclosed all the identifiers.

This is what I have got so far for cluster A extraction:

grep -o "(*(A#.*)*" file1 | sed 's/,*E#.*//g'

but this doesn't applies to clusters that appear more than once in different part of the file, i.e. cluster E in this case. Also, it wasn't actually focus on the number of brackets being extracted, which will cause error on the output file (the number of open brackets and close brackets are different).

sed and perl command doesn't work for me. I tried splitting the file at each comma and extract each subsequent line start with E (to extract the E cluster).

sed 's/,/,\n/g' file1 | sed -n '/*E.*,\n(E/p'
sed -n ':begin;$!N;/*(E#.*\n*(E/p' file1
sed 's/,/,\n/g' file1 | perl -ane 'if(/.*E#.,\n*E#./ ... /^}/){$counter++ if /\(E#/; print if $counter==1}'

I am a bit lost in the process and trying hard to emphasis this in the simplest and shortest way possible. Do let me know if there's anything missed out or part that is less clear.

Answer 1

Could be something like:

<file1 perl -lne '
  for (m{(\((?:[^()]++|(?1))*\))(?(?{($1 =~ s/[^ABE]//gr) !~ /^(.)\1+$/})(*FAIL))}g) {
    ($cluster) = /([ABE])/;
    open($out{$cluster}, ">", "cluster $cluster.txt") unless $out{$cluster};
    print {$out{$cluster}} $_;
  }'

Here using a few of perl's advanced regexp operators:

• (?1) is used for recursive matching so we can say match a pair of (...) containing 0 or more of either a sequence of non-()s or another one of those pairs of (...) containing... and so on.
• (?:...) is just the non-capturing version of (...). Only used for grouping.
• ++ is the non-backtracking version of + (one or more, but don't back track).
• (?(?{code})pattern) inserts pattern in the regexp dynamically if the code succeeds. Here we insert (*FAIL) aka (*F) or (?!) to tell the regexp engine there's no match at this point if the ABE letters in what was matched by the first capture group is not a sequence of two or more of the same letter.

See perldoc perlre for details.

Then it's just a matter of extracting the letter from those matches and write the match in the corresponding output file.

For those not familiar with perl:

• perl -ln is the sed mode where the code (here passed to -e) is run for each line of the input where $_ is the equivalent of sed's pattern space.
• m{regex}g is alternative syntax for /regex/g. In list context, it returns what was matched by all capture groups as separate elements if any, or all matches otherwise (doesn't make any difference here as there's only one capture group and it includes the whole match). Applies to $_ if no subject is specified (with subject =~ m{...}g).
• for (list) {code} is for $var (list) {code} to loop over the elements of a list, but without the variable specified, so it defaults to $_.
• /(ABE)/, same as m{(ABE)}, in list content (here an assignment to a list), here without the g, returns what was matched by the capture group (the first occurrence of a A, B or E letter). Without capture group, it would just return a boolean.
• $1 =~ s/[^ABE]//gr applies the subtitution (globally) and returns the result. So here returns the contents of the capture group with anything but the ABE letters removed.

You can make it slightly more legible by using the x flag which allows inserting spaces and comments and naming your capture groups:

<file1 perl -lne '
  for (
    m{
      (?<paren> [(] (?: [^()] ++ | (?&paren) ) * [)])
      (?(?{ ($+{paren} =~ s/[^ABE]//gr) !~ /^(.)\1+$/ })(*FAIL))
    }xg
  ) {
    ($cluster) = /([ABE])/;
    open($out{$cluster}, ">", "cluster $cluster.txt") unless $out{$cluster};
    print {$out{$cluster}} $_;
  }'

Answer 2

One way can be to write the grammar of the input file structure.

perl -M5.010 -Mautodie -lne 'my $code = 
sub($) {
  qr{
    ((?&list))
    (?(DEFINE)
      (?<element> [$_[0]][#]\d+)
      (?<value> (?:(?&element)|(?&list)))
      (?<list> \((?&value)(?:,(?&value))*\))
    ) #DEFINE
  }x; #qr
}; #sub

for my $v ( qw(A B E) ) {
  my $re = $code->(quotemeta $v);
  open my $fh, ">", "cluster_$v.txt";
  select $fh;
  print for grep(/\S/,/$re/g);
  close $fh;
}' file

---

Notes:-

• If we elongate and view the input file it looks as follows:

sample of file1:
(
  (
    (
      (A#273075,A#273116),
      (
        (A#224325,A#192952),
        A#243232
      )
    ),
    (
      (
        (E#7955,E#7165),
        E#6239
      ),
      E#4530
    )
  ),
  (
    (
     (
       (
         (E#3075,E#3702),
         B#251221
       ),
       E#35128
     ),
     B#243275
   ),
   (
     (B#198094,B#176280),
     B#273119
   )
 )
)

---

• So we see it is essentially a collection of lists or a list of lists.
• Our grammar was based on this observation.

---

Output:- The files cluster_[ABE].txt are created whose combined output is given below.

((A#273075,A#273116),((A#224325,A#192952),A#243232))
((B#198094,B#176280),B#273119)
(((E#7955,E#7165),E#6239),E#4530)
(E#3075,E#3702)