匹配括号kotlin的方式

我给Kotlin一个去; 内容编码，我有一个字符串的ArrayList，我要分类取决于括号如何匹配：

(abcde) // ok characters other than brackets can go anywhere )abcde( // ok matching the brackets 'invertedly' are ok (({()})) // ok )()()([] // ok ([)] // bad can't have different overlapping bracket pairs ((((( // bad all brackets need to have a match 

我的解决方案出来（递归）：

 //charList is a property //Recursion starter'upper private fun classifyListOfCharacters() : Boolean{ var j = 0 while (j < charList.size ) { if (charList[j].isBracket()){ j = checkMatchingBrackets(j+1, charList[j]) } j++ } return j == commandList.size } private fun checkMatchingBrackets(i: Int, firstBracket :Char) : Int{ var j = i while (j < charList.size ) { if (charList[j].isBracket()){ if (charList[j].matchesBracket(firstBracket)){ return j //Matched bracket normal/inverted } j = checkMatchingBrackets(j+1, charList[j]) } j++ } return j } 

这有用，但是这是如何在Kotlin中做到的？ 感觉就像我用Kotlin语法编写了java代码

在递归中发现这个函数式语言更好 ，我尝试过从操作函数的角度来考虑递归，但没有成功。 我很乐意指出正确的方向，代码或可能的重构的一些伪代码。

（省略了一些关于括号的扩展方法，我想这很清楚他们在做什么）

Answer 1

另一个可能是这个问题更简单的方法是在迭代字符的时候保持一堆括号。

当你遇到另一个支架时：

• 如果它匹配堆栈顶部，则弹出堆栈顶部;

• 如果它不匹配堆栈顶部（或堆栈为空），则将其推入堆栈。

如果最后有任何括号保留在栈上，则意味着它们是不匹配的，答案是false 。 如果堆栈结束，答案是true 。

这是正确的，因为一个序列中位置i的括号可以匹配位置j另一个括号，只要它们之间没有不匹配的不同类型的括号（位置k ， i < k < j ）。 堆栈算法精确地模拟了这种匹配的逻辑。

基本上，这个算法可以在一个for循环中实现：

 val stack = Stack<Char>() for (c in charList) { if (!c.isBracket()) continue if (stack.isNotEmpty() && c.matchesBracket(stack.peek())) { stack.pop() } else { stack.push(c) } } return stack.isEmpty() 

_{我已经重用了你的扩展c.isBracket(...)和c.matchesBracket(...) 。 Stack<T>是一个JDK类。}

这个算法隐藏了递归和括号内的括号堆栈的抽象括号。 比较：你当前的方法隐式使用函数调用堆栈而不是括号堆栈，但目的是相同的：它要么找到匹配的顶部字符，要么进行更深的递归调用顶部的另一个字符。

Answer 2

热键的答案（使用for循环）是伟大的。 但是，您要求优化的递归解决方案。 这是一个优化的尾递归函数（注意函数之前的tailrec修饰符）：

 tailrec fun isBalanced(input: List<Char>, stack: Stack<Char>): Boolean = when { input.isEmpty() -> stack.isEmpty() else -> { val c = input.first() if (c.isBracket()) { if (stack.isNotEmpty() && c.matchesBracket(stack.peek())) { stack.pop() } else { stack.push(c) } } isBalanced(input.subList(1, input.size), stack) } } fun main(args: Array<String>) { println("check: ${isBalanced("(abcde)".toList(), Stack())}") } 

该函数调用自身，直到输入变为空，并且如果输入为空时堆栈为空，则返回true。

如果我们查看生成的字节码的反编译的Java等价物，那么这个递归已经被编译器优化为一个有效的while循环，所以我们不会得到StackOverflowException （去除了Intrinsics的空检查）：

 public static final boolean isBalanced(@NotNull String input, @NotNull Stack stack) { while(true) { CharSequence c = (CharSequence)input; if(c.length() == 0) { return stack.isEmpty(); } char c1 = StringsKt.first((CharSequence)input); if(isBracket(c1)) { Collection var3 = (Collection)stack; if(!var3.isEmpty() && matchesBracket(c1, ((Character)stack.peek()).charValue())) { stack.pop(); } else { stack.push(Character.valueOf(c1)); } } input = StringsKt.drop(input, 1); } }