algorithm - 基本递归，检查平衡括号

Question

我过去编写过使用堆栈来检查平衡方程的软件，但现在我被要求递归地编写一个类似的算法来检查正确嵌套的括号和圆括号。

Good examples: () [] () ([]()[])

Bad examples: ( (] ([)]

假设我的函数被调用:isBalanced。

是否应该每次通过评估一个更小的子字符串(直到达到剩余 2 的基本情况)？或者，我应该始终评估完整的字符串并向内移动索引吗？

Answer 1

首先，对于您最初的问题，请注意，如果您使用的是非常长的字符串，您不希望每次进行函数调用时都制作精确的副本减去一个字母。因此，您应该倾向于使用索引或确认您选择的语言没有在幕后进行复制。

其次，我对这里使用堆栈数据结构的所有答案都有疑问。我认为您的作业的重点是让您了解通过递归您的函数调用创建堆栈。您不需要使用堆栈数据结构来保存括号，因为每个递归调用都是隐式堆栈上的新条目。

我将用匹配 ( 和 ) 的 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!