String manipulation via recursion (JS)

Question

I have incoming strings that are formatted using some bracket notation method I haven't seen before (I assume to compress size). Understanding the method itself is straightforward but I'm having trouble turning that into code it out.

Here is a simple example of an incoming string: 'ADFAS[AA,BT]'

This string needs to be parsed so that it results in the array: ['ADFASAA', 'ADFASBT'].

It is important that order is maintained in the resulting array. I'm open to any nice clean answer although I like the idea of an elegant recursive method here. I'm not having luck.

Here is a more complicated example: 'INGFKQRRG[I5EEOR[T,U,V,W],Y5ECOR[T,U]]'

Which should yield the result:

[
  'INGFKQRRGI5EEORT', //--
  'INGFKQRRGI5EEORU', //  \
  'INGFKQRRGI5EEORV', //  / - these are from the first nested level block and its nested letter endings
  'INGFKQRRGI5EEORW', //--

  'INGFKQRRGY5ECORT', //--\
  'INGFKQRRGY5ECORU', //--/ - these are from the second nested level block and its nested letter endings
]

The incoming strings may have multiple nested levels. Ex: 'GMZTAOSIHI[2Q,3[A,Q],4A]' Which should yield:

[
  'GMZTAOSIHI2Q',

  'GMZTAOSIHI3A',
  'GMZTAOSIHI3Q',

  'GMZTAOSIHI4A'
]

Here's the approach I've been taking so far:

A function that finds the outermost bracketed substr

function getInnerBracket(s) {
    const sBracket = s.indexOf('['),
          eBracket = s.lastIndexOf(']');

    return t.slice(sBracket + 1, eBracket);
}

Then I can test the string to see if it has a ], which indicates that within the returned string has multiple parts, some of which may have more nested items.

function testForSubItems(s) {
    return /\],/.test(s)
        ? s.split('],')
        : s;
}

At this point I feel very stuck because I can't figure out how to write one wrapper function to recursively keep track of when to pass it back down to these two helper functions. Every attempt just ends up with logic holes and I'm stuck.

Not an answer, but given that you may have deeply nested text content, JS regex probably isn't the solution for your problem. — Tim Biegeleisen
– Tim Biegeleisen, Commented Mar 12, 2020 at 17:00
"I'm open to any nice clean answer" - And we are open for your attempt to solve this on your own ;) — Andreas
– Andreas, Commented Mar 12, 2020 at 17:01
@TimBiegeleisen From all examples I've seen so far, they don't seem to ever go past 5-6 nested levels. On average they have ~2 nested levels. — Adam Moisa
– Adam Moisa, Commented Mar 12, 2020 at 17:01
@Andreas I have been trying for the past ~2hrs :) thanks for the encouragement tho! — Adam Moisa
– Adam Moisa, Commented Mar 12, 2020 at 17:02
Then you've missed to add those attempts. SO is not meant to be a free coding service. — Andreas
– Andreas, Commented Mar 12, 2020 at 17:03

Kosh · Accepted Answer · 2020-03-12 17:58:39Z

4

The recursive regex solution:

let A = 'INGFKQRRG[I5EEOR[T,U,V,W],Y5ECOR[T,U]]';

const expand = (s) => {
  s = s.replace(
    /([^[,]+)\[([^[\]]+)\]/g, 
    (_, w, px) => px.split(',').map(c => w+c).join(',')
  );
  return s.includes('[') ? expand(s) : s.split(',');
}

console.log(expand(A))
console.log(expand('GMZTAOSIHI[2Q,3[A,Q],4A]'))

edited Mar 12, 2020 at 17:58

answered Mar 12, 2020 at 17:44

Kosh

18.6k2 gold badges24 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Adam Moisa Over a year ago

Wow. I am blown away. This is so concise and clear. Thank you! Tested on one more nested level just to make sure and it worked perfectly! (Ex. 'GMZTAOSIHI[2Q,3[A,Q,C[B,E]],4A]')

Kosh Over a year ago

@AdamMoisa, happy to help!

Collectives™ on Stack Overflow

String manipulation via recursion (JS)

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related