基本递归,检查平衡括号

Question

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

好例子:()[]()([]()[])

不好的例子:((]([)]

假设我的函数被调用: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!

Answer 2

有很多方法可以做到这一点,但最简单的算法是简单地从左向右处理,将堆栈作为参数传递

FUNCTION isBalanced(String input, String stack) : boolean
  IF isEmpty(input)
    RETURN isEmpty(stack)
  ELSE IF isOpen(firstChar(input))
    RETURN isBalanced(allButFirst(input), stack + firstChar(input))
  ELSE IF isClose(firstChar(input))
    RETURN NOT isEmpty(stack) AND isMatching(firstChar(input), lastChar(stack))
      AND isBalanced(allButFirst(input), allButLast(stack))
  ELSE
    ERROR "Invalid character"

这里用Java实现.请注意,为了方便起见,我现在已经切换它,以便堆栈在前面而不是在字符串的后面推送.我还修改了它,以便它只是跳过非括号符号而不是将其报告为错误.

static String open  = "([<{";
static String close = ")]>}";

static boolean isOpen(char ch) {
    return open.indexOf(ch) != -1;
}
static boolean isClose(char ch) {
    return close.indexOf(ch) != -1;
}
static boolean isMatching(char chOpen, char chClose) {
    return open.indexOf(chOpen) == close.indexOf(chClose);
}

static boolean isBalanced(String input, String stack) {
    return
        input.isEmpty() ?
            stack.isEmpty()
        : isOpen(input.charAt(0)) ?
            isBalanced(input.substring(1), input.charAt(0) + stack)
        : isClose(input.charAt(0)) ?
            !stack.isEmpty() && isMatching(stack.charAt(0), input.charAt(0))
              && isBalanced(input.substring(1), stack.substring(1))
        : isBalanced(input.substring(1), stack);
}

测试工具:

    String[] tests = {
        "()[]<>{}",
        "(<",
        "]}",
        "()<",
        "(][)",
        "{(X)[XY]}",
    };
    for (String s : tests) {
        System.out.println(s + " = " + isBalanced(s, ""));
    }

输出:

()[]<>{} = true
(< = false
]} = false
()< = false
(][) = false
{(X)[XY]} = true