Как быстро проверить правильная ли скобочная последовательность?

Question

[Йцу Йцуевич]

Допустим есть некоторая правильная СП — S.
Тогда заменим любую одну её скобку на противоположную ("(" заменим на ")", а ")" на "(").
Теперь S не является правильной скобочной последовательностью.
Далее снова инвертируем какую-нибудь (уже другую) скобку.

Возможно ли на этом шаге за константное время (в крайнем случае, за логарифм-е) проверить последовательность на правильность?

Например:
1. Начало: S = (()())
2. Первая замена — инвертирование символа 3: S = (((())
3. Вторая замена — инвертирование символа 4: S = ((()))

На 1 и 3 шагах СП правильная, а на 2 неправильная.
Возможна ли проверка не за линейное время?

UPD:
Известна позиция инвертируемой скобки

Comments

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

известно, какие скобки заменили, или дана СП, где заменили неизвестные две скобки?

[Йцу Йцуевич]

Да, индекст известен!
Забыл уточнить в вопросе.

[d-stream]

Гм... а "правильная" скобочная последовательность - это классическое "все открывающие скобки закрыты"?

Если да - то проверяем условие равенства количества открывающих и закрывающих скобок.

[Артём Токаревских]

d-stream: А если начинается с закрывающей скобки?

[d-stream]

Артём Токаревских: тогда можно прерываться сразу + так же по последней скобке

[Артём Токаревских]

d-stream: А если окрывающая скобка и за ней две закрывающих?

Но где-то здесь ключ к решению и зарыт

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

Йцу Йцуевич: известна вся история инвертирования скобок, начиная с начальной правильной СП или только предыдущая итерация?

[Йцу Йцуевич]

Даже храня количество откр. и закр. скобок, в худшем случае всё равно придётся пройтись по всей последовательности-1.
Пример (пробелы расставлены для читабельности):
( () ) () () )(

[Йцу Йцуевич]

Сергей Соколов ну, это не сильно важно. Например, допустимо однажды пройтись по всей последовательности.
Но, для упрощения, пусть изначально последовательность правильная!

Answer 1

[Андрей]

Единственное условие корректности - счет кол-ва закрытых скобок не должен превышать счета открытых. Храните для каждой позиции адрес ближайшей справа с единичной ("+1") или нулевой ("0") суммой счета. Поскольку инверсия с открывающей на закрывающую уменьшает все счетчики вправо до второй инверсии на "-2", Вам остается проверить была ли вторая инверсия парной, и не оказалось ли ячейки единичного/нулевого счета между ними.
P.S. Парная инверсия, в которой левая замена с закрывающей на открывающую, как у Вас в примере, кажется мне валидной всегда.

Comments

[Йцу Йцуевич]

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

Теперь по вашему ответу: если изменять все счетчики, не получим ли мы линейное время в худшем случае?
Хорошо, возьмём простой случай: первая инверсия меняет закр. на откр., вторая — откр. на закр. причём правее от места предыдущей инверсии. Тогда последовательность сохранит свой статус после двух таких замен. Вы помогли мне понять это! Но как сюда приставить счётчики, сделав алгоритм не линейным — пока не понял.

[Андрей]

> количество открытых и закрытых должно быть равным
Вы же говорите, что исходно у Вас правильная последовательность ? Парная инверсия не изменит общий счет скобок.

> счет кол-ва закрытых скобок не должен превышать счета открытых
Я имел в виду именно счет (т.е. инкрементальный счетчик их суммы слева от текущей позиции), а не количество.

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

[Йцу Йцуевич]

Может кому-то ваш способ поможет.
Но увы не мне, — как проверка, так и замена в моём случае выполняются много раз.

Answer 2

[Сергей]

Проблема в том что:
1. Пусть у вас уже есть структура в памяти, которая как-то позволяет вам определить правильность за n*log(n).
2. Вы изменили скобочку ( в самом начале.
3. Теперь у вас уже есть новая последовательность, вы должны изменить свою структуру так, чтобы она отвечала правильно уже о новой последовательности.
4. Но чтобы изменить, вы очевидно должны прости по всем оставшимся справа скобочкам, т.к. измененная скобка изменяет значения скобок справа, но не меняет ничего слева.
5. Чтобы пройти вам нужно время O(n).
6. Таким образом, такой структуры нет :Р

Ловко я вам доказал. Да ?

Comments

[Дима Петров]

но вообще просто есть программы с подсветкой синтаксиса, которые могут подсветить проблемку с незакрытой скобкой.

[Mercury13]

Доказательство попазхивает демагогией.

[Йцу Йцуевич]

Сергей Не доказали.
1. Структура должна знать, является ли СП правильной в каждый момент времени, а не определять по запросу. Т.е. можно считать, что изменении скобки (в этой структуре) производится за log(n), а получение результата за O(1).

Далее можно не продолжать, но всё же:
4. Не очевидно. В моём примере со второй заменой мы точно знаем, что последовательность не является правильной!
После третей — она точно правильна в случаях, когда:
первая замена изменила закр. на откр., а вторая изменила откр. на закр., причём в позиции не левее первой замены (как раз в моём примере);
первая замена изменила откр. на закр., вторая закр. на откр., причём в позиции не правее первой замены.

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

Недопонял фразу: "изменяет значения справа". Если мы изменили откр. на закр., то что она изменит справа?

5. Сложность поиска в отсортированном массиве не требует O(n).

Ловко, но не доказали.

P.S. Но мысль интересная. В любом случае, спасибо!

[Артём Токаревских]

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

[Йцу Йцуевич]

в принципе, да!

Answer 3

[Mercury13]

Критерий таков.
1. Баланс ( и ) должен сохраниться.
2. а) Либо вырожденный случай (скобку меняем дважды на противоположную);
б) либо ) → ( идёт перед ( → );
в) либо уровень вложенности обеих скобок не менее 3, при этом они сидят в общих скобках 2-го уровня.

Из-за 2в без предобработки за O(n) проверить невозможно. Но предобработка хороша, если мы решаем кучу таких запросов, и с этим отдельный вопрос. В таком случае, вероятно, лучше использовать дерево отрезков, обрабатывающее каждый запрос за log n. Пока мне алгоритм понятен не до конца; если вы скажете, что действительно задача про кучу запросов — подумаю..

Answer 4

[Labunsky]

1. Если изначально последовательность правильная - любая инверсия приводит к ее порче;
   
2. Если инверсии было две - последовательность может быть правильной, только когда
   

• Инвертировались скобки разного типа ('(' и ')')
  
• Между ними должно быть четное количество других скобок
  

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

1. Предположим, что скобочная последовательность хранится в виде массива, элементами которого являются скобки, для каждой из которых хранится индекс ее пары (соответствующей закрывающей/открывающей скобки)
   
2. При каждой инверсии будем затирать для соответствующих скобок (открывающая/закрывающая) индексы и помечать их
   
3. Так как инверсии было две, то получим 4 помеченных индекса. В силу того, что инвертировались разные типы скобок, среди них будут либо образовываться две новые пары, не противоречащие правильности последовательности (проверяется это травиально), либо нет
   

Быстрее ничего придумать не получается. Единственное тонкое место - проверка в последнем пункте, так как в различных случаях может занимать как константное время, так и O(k), где k строго меньше n и в среднем случае является логарифмом.

Comments

[Йцу Йцуевич]

Возможно плохо понял, но вот пример:
()()() старт
()))() инв. 3 символа
())(() инв. 4 символа
Инвертировались скобки разного типа — Верно
Между инвертируемыми скобками нет символов (хотя, заметим, можно вставить любую ПСП, это не изменит результат), т.е. 0 — чётное число — Верно

Итого: СП не является правильной

[Labunsky]

Йцу Йцуевич: предполагается, что за один шаг инвертируется только одна скобка, как в примере из вопроса. Проверка, соответственно, производится только после второй инверсии (после первой она гарантировано неправильна).

Пример из комментария алгоритмом можно обработать, если разбить его на шаги (но тогда она будет производиться более одного раза, асимптотика испортится). Проверка же после произвольного числа инверсий невозможна за асимптотику меньшую, чем O(n). В лучшем случае можно отсеить за константное время часть случаев, но это и все