brackets.md

Последовательность скобок

Вы пишите текстовый редактор с крутой подсветкой синтаксиса. Вы хотите исправлять ошибки программиста, в том числе неправильно расставленные скобки.

Напишите функцию, которая будет исправлять последовательность скобок, используя минимальное количество изменений. Возможные скобки [], (), {}, <>. Интуитивно понятно, что такое правильная последовательность, однако более формальное определение, а так же основные методы работы с ними можно найти тут.

Метод должен принимать строку, состоящую только из разрешенных скобок, и возвращать строку той же длины, содержащую правильную последовательность скобок. Изменений нужно сделать как можно меньше.

Изменять можно только закрывающие скобки, т.е. ]})>. Открывающие скобки должны остататься без изменений. Если исправить строку невозможно, верните null.

Примеры

correctBrackets("[}"); // "[]"
correctBrackets("[()}"); // "[()]"
correctBrackets("[[[)])"); // "[[[]]]"
correctBrackets("<{[(>}])"); // "<{[()]}>"
correctBrackets("]]"); // null
correctBrackets("[[[))"); // null
correctBrackets("{((])]"); // "{(())}"

Решение

Попробуем сделать так - сначала определить, можем ли мы вообще получить корректную последовательность, и если да, то уже составить ее. Как это определить? Попробуем просто посчитать количество открывающих и закрывающих скобок, и если они равны - значит последовательность составить можно.

function correctBrackets(brs){
  let opening = {
    '[': ']',
    '{': '}',
    '(': ')',
    '<': '>',
  };

  let open = 0, close = 0;

  for(let i = 0; i < brs.length; i++){
    let c = brs[i];
    if(opening[c]){
      open++;
    } else {
      close++;
    }
  }

  if(open != close){
    return null;
  }

  // Составляем последовательность
}

Однако легко придумать строку, которая будет ложно распознана как верная, например ][. Обратившись к формальному определению, можно заметить ...любой префикс которой содержит количество открывающих скобок, больше или равное закрывающим.... Под префиксом здесь имеется ввиду любая подстрока, начало которой совпадает с началом исходной строки (обратное префиксу - суфикс: любая подстрока, конец которой совпадает с концом исходной строки). Таким образом, в наш код нужно добавить такую проверку.

function correctBrackets(brs){
  let opening = {
    '[': ']',
    '{': '}',
    '(': ')',
    '<': '>',
  };

  let open = 0, close = 0;

  for(let i = 0; i < brs.length; i++){
    let c = brs[i];
    if(opening[c]){
      open++;
    } else {
      close++;
    }

    if(open < close){
      return null;
    }
  }

  if(open != close){
    return null;
  }

  // Составляем последовательность
}

Теперь напишем код для составления самой последовательности. Воспользуемся структурой данных стек - одну из самых важных структур в работе со строками и теории формальных языков в общем. Будем формировать правильную строку с нуля. Если встретим открывающую скобку - положим ее наверх стека и добавим к возвращаемой строке. Если закрывающую - посмотрим, какая была последняя "неудовлетворенная" открывающая скобка, и поставим нужную скобку. Например, в строке "([]." на месте точки последняя "неудовлетворенная" скобка это "(".

  ...
    let stack = [];
    let ret = '';

    for(let i = 0; i < brs.length; i++){
      let c = brs[i];

      if(opening[c]){
          stack.push(c);
      } else {
          let br = stack.pop();

          c = opening[br];
      }

      ret += c;
    }

    return ret;
    ...

Все хорошо, и работает. Однако код получился громоздким, и создается ощущение, что мы делаем много лишних движений. Попробуем избавиться от проверки строки на правильность, и сразу формировать строку, по ходу дела понимая, если составить правильную последовательность скобок не получится. Что будет, если в строке let br = stack.pop(); стек окажется пустым? Это означает, что мы уже "удовлетворили" все открывающие скобки, и при этом встретили еще одну закрывающую скобку. Например, если на месте точки "[[]]." стоит закрывающая скобка - такая строка некорректна. Также, что произойдет для строки "[[["? После формирования, на стеке все еще будут "неудовлетворенные" открывающие скобки. Такая строка тоже некорректна.

function correctBrackets(brs){
    let opening = {
      '[': ']',
      '{': '}',
      '(': ')',
      '<': '>',
    };

    let stack = [];
    let ret = '';

    for(let i = 0; i < brs.length; i++){
      let c = brs[i];

      if(opening[c]){
        stack.push(c);
      } else {
        if(stack.length === 0){
            return null;
        }

        let br = stack.pop();

        c = opening[br];
      }

      ret += c;
    }
    if (stack.length > 0){
      return null;
    }
}

Из хороших решений стоит отметить решение Евгения Зайцева.