//Check for balanced parenthesis without using stack: DOUBT
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之后所做的逻辑。
我知道一个循环是用来遍历数组的，但是我不知道它是如何在合适的位置找到右括号的。
帮助。
使用无堆栈的递归检查平衡的假命题
代码没有使用显式的堆栈数据结构，但它绝对使用堆栈:调用堆栈。每个方法调用都涉及到堆栈上的一次push(或者可能不止一次，取决于您如何描述事物)，并且每个方法返回都涉及到一个相应的pop(或多个pop)。
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--; } }
向前扫描字符序列，查找与序列的初始字符匹配的结束分隔符。变量count提供处理与当前处理的括号类型相同的嵌套括号对。其他类型的括号此时将被忽略。当循环结束时，i是匹配的右括号的索引，或者等于序列的长度，n不是数组的有效索引。
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);
当且仅当当前括号对之间的子序列是平衡的且序列尾部是平衡的
整个序列是平衡的。