Скобки в рукописи
Редактор вычитывает электронную рукопись и хочет, чтобы программа сразу показала место, где скобки и кавычки перепутаны. Пары такие: ( ), [ ], { }, « » и „ “ — последние ставят для кавычек внутри кавычек. Правильно, когда каждая закрывающая закрывает последнюю ещё не закрытую открывающую того же вида и в конце открытых не остаётся: «(«да»)» — правильно, «(«да)»» — нет.
Найдите первую ошибку. Три теста — настоящие главы «Войны и мира» из электронного текста, по которому работает песочница сайта; в одной из них ошибка есть на самом деле.
Вход
Текст в кодировке UTF-8, до 10⁶ символов, в нескольких строках. Все символы, кроме десяти перечисленных скобок, — обычный текст.
Выход
YES, если скобки расставлены правильно. Иначе NO p, где p — номер символа с ошибкой, считая с 1 и считая все символы, включая пробелы и переводы строк. Ошибка — первая закрывающая скобка, которой нечего закрыть: открытых нет или последняя открытая другого вида. Если таких нет, но в конце остались открытые, ошибка — самая первая из оставшихся открытых.
Примеры
Пример 1
Он сказал («да» [и нет]) — и ушёл.
YES
Пример 2
Наташа (как всегда «весело) ответила».
NO 27
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы вид скобок был один, хватило бы счётчика: плюс один на открывающую, минус один на закрывающую, и счётчик не должен уходить в минус. Почему для пяти видов не хватит пяти счётчиков? Посмотрите на второй пример.
2Подсказка 2
Закрывающая скобка должна закрыть последнюю открытую. Какая структура данных помнит, что открыто последним, и умеет это быстро забыть?
3Идея
Стек. Открывающую кладём на стек вместе с её номером. Закрывающая смотрит на вершину: если стек пуст или наверху скобка другого вида — это первая ошибка. Иначе снимаем вершину. Если текст кончился, а стек не пуст, ошибка — его дно: самая ранняя из незакрытых.
4Разбор
Один проход по тексту. В стеке храним номера открывающих скобок, вид берём из текста по номеру (или храним рядом). Пять счётчиков из первой подсказки ломаются на «(«)»»: каждый вид по отдельности сбалансирован, но скобки перекрещиваются, и счётчики этого не видят.
На третьем тесте стек находит настоящую ошибку оцифровки: в главе об охоте стоит «как и всегда в (своих суждениях…», и эта скобка в главе не закрывается. В статье видно, что делает такая скобка со всем романом: её случайно «закрывает» номер пункта «1)» в четвёртом томе, через миллион с лишним символов. На пятом тесте ошибка формальная: «1)» в перечне масонских добродетелей — номер, а не скобка, но по правилам задачи это закрывающая без пары. Настоящей программе вычитки пришлось бы знать и такое.
Позиции — в символах, а не в байтах. В Python строка после decode индексируется символами. В Go for _, ch := range s перебирает символы, но первый возвращаемый индекс — номер байта, а русская буква в UTF-8 занимает два байта; номер нужно считать отдельно.
4+Решение
5Сложность
O(n) времени: каждый символ смотрим один раз, каждая скобка кладётся на стек и снимается не больше раза. Память — O(n) в худшем случае, когда все скобки открывающие.
6Типичные ошибки
- Счётчики вместо стека. Пропускают перекрещенные скобки — второй пример.
- Рекурсия. Девятый тест — четверть миллиона вложенных скобок: глубины рекурсии Python не хватит, а явный стек справится.
- Номер байта вместо номера символа. В Go индекс в
rangeпо строке — байтовый; на русском тексте ответ уедет почти вдвое. - Не та незакрытая. Если в конце открыто несколько скобок, нужна первая (дно стека), а не последняя.