Как сделать анализ скобок в тексте?

Question

[nnvJS]

Необходим фрагмент кода на js, который определяет открывающую и закрывающую скобку и возвращает индексы в таком фрагменте текста.
Например:
Входной текст: "{{}{}{{}}}".
Результат: [[0,9],[1,2],[3,4],[5,8],[6,7]].
Код должен определять вложенность элементов друг в друга и, учитывая эти данные, возвращать массив пар чисел.
Не обязательно на js. Буду рад даже идеям как это реализовать, а также подобным алгоритмам на других языках программирования.

Comments

[Сергей Соколов]

разбор на GeeksForGeeks (на англ.)

Answer 1

[0xD34F]

Есть такая структура данных - стек называется.

При встрече открывающей скобки добавляем в результирующий массив пару индексов - открывающей и закрывающей скобок. Второе значение, так как закрывающей скобки ещё нет, пока будет null. В стек сохраняем индекс, под которым добавленная пара оказалась в массиве с результатами.

Встретили закрывающую скобку - извлекаем из стека индекс последнего неполного результата, заменяем там null на индекс встреченной скобки. Конечно, если в стеке что-то есть. Если стек пустой - значит, у встреченной закрывающей скобки не было соответствующей ей открывающей, добавляем в результирующий массив пару из null и текущего индекса.

function bracketIndices(str) {
  const stack = [];
  const result = [];

  for (let i = 0; i < str.length; i++) {
    if (str[i] === '{') {
      stack.push(result.push([ i, null ]) - 1);
    } else if (str[i] === '}') {
      if (stack.length) {
        result[stack.pop()][1] = i;
      } else {
        result.push([ null, i ]);
      }
    }
  }

  return result;
}


bracketIndices('{}{{{}}}') // [[0,1],[2,7],[3,6],[4,5]]
bracketIndices('---}{{}{') // [[null,3],[4,null],[5,6],[7,null]]
bracketIndices('fuck off') // []

Comments

[nnvJS]

Спасибо