Ответ 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;
}
Примечание.. Оба вышеприведенных примера предполагают, что скобки сбалансированы, поэтому проверка границ массива не выполняется. Реальная реализация проверит, что вы не сбегаете с конца массива и не генерируете исключение (или возвращаете код ошибки), который указывает, что скобки не сбалансированы во входном тексте, если вы это сделаете.