Эффективный алгоритм автоматического завершения скобок

Question

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

Однако этот подход кажется медленным для больших исходных файлов (> 1 МБ), особенно когда новая строка добавляется в первой половине строк исходного текста (новая строка в первой строке = наихудший случай = весь текст сканируется). Некоторые IDE имеют эту возможность и могут быстро ее обработать, поэтому они должны использовать другой подход. Итак, я хотел бы знать, какой алгоритм они используют или какой-либо другой подход лучше моего.

Answer 1

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

например. Вы можете построить дерево, которое хранит begin_pos / end_pos для пары скобок внутри узла и в качестве дочерних для всех пар скобок внутри. Будьте особенно осторожны с несоответствующими скобками (т. Е. Они начинаются / заканчиваются на границах родителей).

Добавление дополнительной скобки открытия / закрытия довольно удобно для такой структуры, поскольку вы можете пропустить все дочерние и родные деревья.

Соответствующая реализация должна работать с решением O (log (n)), где n - число пар скобок.