递归无栈实现括号匹配：循环逻辑疑问求助

代码片段 #

// 不使用栈检查括号匹配：疑问点
static char findClosing(char c) {
    if (c == '(')
        return ')';
    if (c == '{')
        return '}';
    if (c == '[')
        return ']';
    return Character.MIN_VALUE;
}

static boolean checkBracket(char[] arr, int n) {
    if (n == 0)
        return true;
    if (n == 1)
        return false;
    if (arr[0] == ')' || arr[0] == '}' || arr[0] == ']')
        return false;
    
    char closing = findClosing(arr[0]);
    int i, count = 0;
    
    for (i = 1; i < n; i++) {
        if (arr[i] == arr[0])
            count++;
        if (arr[i] == closing) {
            if (count == 0)
                break;
            count--;
        }
    }
    
    if (i == n)
        return false;
    if (i == 1)
        return checkBracket(Arrays.copyOfRange(arr, i + 1, n), n - 2);
    return checkBracket(Arrays.copyOfRange(arr, 1, i), i - 1) && checkBracket(Arrays.copyOfRange(arr, (i + 1), n), n - i - 1);
}

用户疑问 #

我无法理解初始化变量count和i之后的逻辑。
我知道这段代码通过循环遍历数组，但不清楚该循环如何找到对应位置的闭合括号，请求技术帮助。

核心循环逻辑拆解 #

这段代码用递归+计数替代栈实现括号匹配，核心是精准定位当前开括号对应的闭合括号，具体逻辑如下：

1. 变量作用

   • closing：存储当前第一个开括号对应的闭合括号（比如第一个是(，就对应)）
   • count：统计嵌套的同类型开括号数量，用来处理多层嵌套场景
   • i：遍历数组的索引，从第一个字符的下一位开始

2. 遍历匹配过程

   • 遇到和第一个字符相同的开括号（比如第一个是(，又碰到(）：count加1，代表出现了内层嵌套的同类型括号，需要先匹配内层的闭合括号
   • 遇到closing对应的闭合括号时：
     • 如果count为0：说明这就是和第一个开括号对应的外层闭合括号，直接跳出循环，此时i就是该闭合括号的索引
     • 如果count大于0：说明这是内层嵌套括号的闭合，count减1，继续遍历找外层的闭合括号

3. 后续递归处理

   • 若i == n：遍历完整个数组都没找到对应闭合括号，直接返回false
   • 若i == 1：第一个开括号和紧邻的下一个字符就是一对（比如()），递归检查剩下的子数组
   • 其他情况：把数组拆成两部分递归检查——第一部分是第一个开括号到对应闭合括号之间的子数组（内层嵌套内容），第二部分是闭合括号之后的子数组（后续未检查内容），只有两部分都匹配才返回true

举个实际例子：对于数组[{()}]

• 第一个字符是[，对应的closing是]
• 遍历到{、(、)、}时都不触发匹配逻辑，直到遇到]时，count始终为0，跳出循环，i定位到]的索引
• 随后递归检查{()}子数组和空数组，重复上述逻辑完成匹配

内容的提问来源于stack exchange，提问作者Om Kumar Rath