匹配kotlin方式

Question

我给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类.}

该算法隐藏了递归和括号嵌套在括号堆栈抽象内的括号.比较:您当前的方法隐式使用函数调用堆栈而不是括号堆栈,但目的是相同的:它要么找到顶部字符的匹配项,要么在顶部用另一个字符进行更深层次的递归调用.