Analyse d'une chaîne de caractères avec des parenthèses imbriquées

Question

J'essaie d'analyser une chaîne de caractères avec des parenthèses à l'intérieur de parenthèses. Tant que la chaîne à analyser est assez petite et qu'il n'y a pas trop de parenthèses imbriquées, tout fonctionne bien.

Mais, lorsque la chaîne à analyser devient volumineuse, je continue à obtenir des erreurs du type FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory y RangeError: Maximum call stack size exceeded .

Quelqu'un peut-il me dire comment je peux optimiser/corriger le code ci-dessous pour qu'il fonctionne sur des chaînes de plus grande taille sans erreurs de mémoire et de taille de pile ? La grande chaîne de caractères que j'essaie d'analyser peut être trouvée aquí

L'objectif est d'obtenir une chaîne de caractères ressemblant à ceci

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

À cet effet

[
  '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)

Answer 1

J'opterais plutôt pour une analyse linéaire - Organiser tous les caractères du fichier en une seule fois. Aucune regex n'est nécessaire. Non seulement le programme est plus rapide (et capable d'analyser votre gros fichier texte), mais il est aussi un peu plus joli.

Voici un exemple :

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))