Какие есть способы решить задачу проверки скобок за один проход?

Объяснение концепции

Задача проверки скобок заключается в том, чтобы определить, правильно ли расставлены скобки в строке. Классическое решение использует структуру данных стек, которая работает по принципу LIFO (последним пришёл — первым вышел). Это позволяет проверить баланс за один проход по строке, что даёт временную сложность O(n) и пространственную O(n) в худшем случае.

Как это работает

Алгоритм проходит по каждому символу строки:

• Если символ — открывающая скобка (например, '(', '{', '['), он помещается в стек.
• Если символ — закрывающая скобка, проверяется, не пуст ли стек, и соответствует ли верхний элемент стека этой закрывающей скобке. Если да, верхний элемент удаляется из стека. Если нет — строка невалидна.

После обработки всех символов стек должен быть пустым, иначе скобки не сбалансированы.

Пример кода на JavaScript

function isValid(s) {
  const stack = [];
  const map = { ')': '(', '}': '{', ']': '[' };

  for (let char of s) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else {
      if (stack.length === 0 || stack.pop() !== map[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

Применение

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

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