Подтвердить что ты не робот

Как найти позицию совпадающих скобок или фигурных скобок в данном фрагменте текста?

У многих текстовых редакторов и IDE есть функция, которая выделяет совпадающие скобки, квадратные скобки или фигурные скобки, когда курсор помещается поверх символа открытия или закрытия одной из этих пар.

Какой алгоритм используется для нахождения позиции совпадающей скобки, учитывая положение открытой или закрывающей скобки в текстовом файле? Имейте в виду, что эти символы могут быть вложенными, поэтому просто сканирование вперед или назад по тексту до тех пор, пока вы не найдете противоположного символа.

Пример:

Недавно я столкнулся с этой проблемой при написании интерпретатора brainf * ck на Java. [ и ] на этом языке аналогичны циклу while и могут быть вложенными. Интерпретатору необходимо найти соответствие [ или ] в зависимости от значения в указателе данных. См. примерный код ROT13 для иллюстрации вложенности.

4b9b3361

ОТВЕТЫ

Ответ 1

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

  • Инициализировать счетчик на 1.
  • Прокрутите вперед (вправо) текст.
    • Если встречается другая открытая скобка, увеличьте счетчик.
    • Если встречается закрывающая скобка, уменьшите счетчик.
  • Когда счетчик достигнет нуля, вы нашли соответствующие закрывающие круглые скобки.

В коде это выглядит примерно так:

public int findClosingParen(char[] text, int openPos) {
    int closePos = openPos;
    int counter = 1;
    while (counter > 0) {
        char c = text[++closePos];
        if (c == '(') {
            counter++;
        }
        else if (c == ')') {
            counter--;
        }
    }
    return closePos;
}

Алгоритм поиска положения совпадающей открытой круглой скобки с учетом закрывающей скобки является противоположным.

  • Инициализировать счетчик на 1.
  • Прокрутите назад (влево) текст.
    • Если открытая скобка встречается, уменьшите счетчик.
    • Если встречается закрывающая скобка, увеличьте счетчик.
  • Когда счетчик достигнет нуля, вы нашли совпадающие открытые круглые скобки.

В коде:

public int findOpenParen(char[] text, int closePos) {
    int openPos = closePos;
    int counter = 1;
    while (counter > 0) {
        char c = text[--openPos];
        if (c == '(') {
            counter--;
        }
        else if (c == ')') {
            counter++;
        }
    }
    return openPos;
}

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