Parsing string with nested parentheses

user_9225753 0
Viewed 250

I am trying to parse a string with parentheses inside parentheses. As long as the string to parse is pretty small and don't have to many nested parentheses everything is working fine.

But, when the string to parse get big I keep getting errors like FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory and RangeError: Maximum call stack size exceeded.

Can anyone tell me how I can optimize/fix the code below so it works on strings of bigger size without memory and stack size errors? The big string I am trying to parse can be found here

The goal is to turn a string looking like this

"Alvor (Alv Alf Alvaro (Halfrid Halvar Halvard (Alvilde Alva (Alfie Alvor Joralv) Alfonse)) Calvin (Tjalve Alvbert Alvard))"

To this

[
  'Alvor',
  '(Alv Alf Alvaro  Calvin )',
  '(Halfrid Halvar Halvard )(Tjalve Alvbert Alvard)',
  '(Alvilde Alva  Alfonse)',
  '(Alfie Alvor Joralv)'
]

let alver = "Alvor (Alv Alf Alvaro (Halfrid Halvar Halvard (Alvilde Alva (Alfie Alvor Joralv) Alfonse)) Calvin (Tjalve Alvbert Alvard))";

let open = 0;
const tree = [];

tree[0] = alver.match(/([a-zA-Z])+/)[0];

const processText = (string) => {
    let change = false;
    for(let i = 0; i < string.length; i++) {
        if(string[i] === "(") {
            open++;
        } else if(string[i] === ")") {
            change = true;

            // find inner most () and assign in to its position in the tree array
            tree[open] = tree[open] ?
                tree[open] + string.match(/\([a-zA-Z ]+\)/)[0] :
                string.match(/\([a-zA-Z ]+\)/)[0];

            open--;
            break;
        }
    }

    if(change) {
        open = 0;
        // run again with current inner most () removed
        processText(string.replace(/\([a-zA-Z ]+\)/, ""));
    }
}

processText(alver);

console.log(tree)
parsing javascript
1 Answers

I would opt to parse it in a linear fashion instead - Organize all of the characters in the file in a single sweep. No regex necessary. It not only makes it run faster (and capable of parsing your large textfile), but it looks a little nicer too.

Here's an example:

const data = 'Alvor (Alv Alf Alvaro (Halfrid Halvar Halvard (Alvilde Alva (Alfie Alvor Joralv) Alfonse)) Calvin (Tjalve Alvbert Alvard))'

function processText(text) {
  const levels = []
  let depth = 0
  for (const c of text) {
    if (c === '(') depth++
    if (depth >= levels.length) levels.push([])
    levels[depth].push(c)
    if (c === ')') depth--
  }
  return levels.map(level => level.join(''))
}

console.log(processText(data))

user_76962230
Related