Основная рекурсия, проверьте сбалансированную круглую скобку

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

В большинстве языков программирования, в которых есть неизменяемые строки, вероятно, более затратно (с точки зрения производительности) сократить строку, чем передать в стек строку немного большего размера. С другой стороны, на таком языке, как C, вы можете просто увеличить указатель в массиве char. Я предполагаю, что в значительной степени зависит от языка, какой из этих двух подходов более «эффективен». Оба они эквивалентны с концептуальной точки зрения.

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

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

Я продемонстрирую это с помощью программы 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!

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

Это должно быть простое использование стека ..

private string tokens = "{([<})]>";        
    Stack<char> stack = new Stack<char>();   

    public bool  IsExpressionVaild(string exp)
    {
        int mid = (tokens.Length / 2)  ;  

        for (int i = 0; i < exp.Length; i++)
        {
            int index = tokens.IndexOf(exp[i]);
            if (-1 == index) { continue; }

            if(index<mid ) stack .Push(exp[i]);
            else 
            {
                if (stack.Pop() != tokens[index - mid]) { return false; }       

            }          

        }
        return true;       

    }