Во-первых, к вашему первоначальному вопросу, просто имейте в виду, что если вы работаете с очень длинными строками, вам не нужно делать точные копии без одной буквы каждый раз, когда вы делаете вызов функции. Поэтому вы должны предпочесть использование индексов или убедиться, что выбранный вами язык не делает закулисных копий.
Во-вторых, у меня проблема со всеми ответами, которые используют структуру данных стека. Я думаю, что смысл вашего назначения в том, чтобы вы поняли, что с помощью рекурсии ваши вызовы функций создают стек . Вам не нужно использовать структуру данных стека для хранения скобок, потому что каждый рекурсивный вызов является новой записью в неявном стеке.
Я продемонстрирую программу на C, которая соответствует ( и ). Добавление других типов, таких как [ и ], является упражнением для читателя. Все, что я поддерживаю в функции, это моя позиция в строке (передается как указатель), потому что рекурсия - это мой стек.
/* Search a string for matching parentheses. If the parentheses match, returns a
* pointer that addresses the nul terminator at the end of the string. If they
* don't match, the pointer addresses the first character that doesn't match.
*/
const char *match(const char *str)
{
if( *str == '\0' || *str == ')' ) { return str; }
if( *str == '(' )
{
const char *closer = match(++str);
if( *closer == ')' )
{
return match(++closer);
}
return str - 1;
}
return match(++str);
}
Проверено с этим кодом:
const char *test[] = {
"()", "(", ")", "", "(()))", "(((())))", "()()(()())",
"(() ( hi))) (())()(((( ))))", "abcd"
};
for( index = 0; index < sizeof(test) / sizeof(test[0]); ++index ) {
const char *result = match(test[index]);
printf("%s:\t", test[index]);
*result == '\0' ? printf("Good!\n") :
printf("Bad @ char %d\n", result - test[index] + 1);
}
Выход:
(): Good!
(: Bad @ char 1
): Bad @ char 1
: Good!
(())): Bad @ char 5
(((()))): Good!
()()(()()): Good!
(() ( hi))) (())()(((( )))): Bad @ char 11
abcd: Good!