Scala返回值与预期值不同

Question

我正在学习Scala并编写一个函数（递归）来计算括号的数目：打开+1，关闭-1，以匹配和平衡列表中的所有圆括号的字符。如果括号是平衡的，它应该返回0。

我想出了（与众多打印报表来了解这是怎么回事）：

def countPar(charList: List[Char], count: Int): Int = { 

    if (count < 0) { 
    println("negative count, returning", count) 
    count 
    } 
    else if (charList.isEmpty) { 
    println("empty list, returning", count) 
    count 
    } 
    else if (charList.head.equals('(')) { 
    println("head is ", charList.head, " count + 1:", count + 1) 
    count + countPar(charList.tail, count + 1) 
    } 
    else if (charList.head.equals(')')) { 
    println("head is ", charList.head, " count - 1:", count - 1) 
    count + countPar(charList.tail, count - 1) 
    } 
    else { 
    println("head is ", charList.head, " count:", count) 
    countPar(charList.tail, count) 
    } 
} 

val parCount = countPar("(a(b)c)".toList, 0) 

println(parCount) 

打印报表做似乎证实了逻辑来工作，但是最终的返回值是错误的：

(head is ,(, count + 1:,1) 
(head is ,a, count:,1) 
(head is ,(, count + 1:,2) 
(head is ,b, count:,2) 
(head is ,), count - 1:,1) 
(head is ,c, count:,1) 
(head is ,), count - 1:,0) 
(empty list, returning,0) 
parCount: Int = 4 

我在想什么？

Answer 1

问题在于简单地返回count + countPar(charList.tail, count + 1)而不是countPar(charList.tail, count + 1)（对于右括号也是类似的）。

递归函数的要点在于，根据头值更新计数，并将其传递给递归调用，递归调用将根据尾值对其进行更新（并且递归调用将执行相同的操作，直到尾巴是空的）。这意味着递归调用将返回正确的结果：不需要添加任何内容。

编辑： 我认为一旦重构像这样它也变得更清晰（的重要组成部分，是一个与评论，我尽量不改变，否则你的方法）：

def countPar(charList: List[Char], count: Int): Int = { 
    if (count < 0) { 
    println("negative count, returning", count) 
    count 
    } else if (charList.isEmpty) { 
    println("empty list, returning", count) 
    count 
    } else { 
    val updatedCount = 
     if (charList.head.equals('(')) 
     count + 1 
     else if (charList.head.equals(')')) 
     count - 1 
     else 
     count 
    println(s"head is ${charList.head}, count: ${updatedCount}") 
    // We see here that the reursive call is the same in the 3 cases: the 
    // only difference is how we update the count 
    countPar(charList.tail, updatedCount) 
    } 
} 

Answer 2

你当前编码以非常必要/面向对象的风格。但是这需要一个功能，递归方法：

def isBalanced(string: List[Char], count: Int=0): Boolean = { 
    if (count < 0) { false } // We can only be balanced if (precedes) 
    else { 
    string match { 
     case Nil => count == 0 // Is the count 0? If so, however we got here was balanced! 
     case '('::tail => isBalanced(tail, count + 1) // (prepended to some list 
     case ')'::tail => isBalanced(tail, count - 1) //) prepended to some list 
     case _::tail => isBalanced(tail, count) 
    } 
    } 
} 

请注意，我们的外部函数回答与它的招牌的问题：给定的任意字符的列表时，该列表平衡？ （'yes or no'意味着一个布尔值：使用一个整数使得这个函数的用户变得复杂）。与所有的递归函数一样，函数会问这个问题是否可以被平凡地解决，如果不是，它会做一些工作然后简单地返回递归调用的结果。

为此，我们首先定义一个基例。也就是说，如果列表为空，我们只需返回计数是否为0.如果是，我们知道参数是平衡的。

其次，我们定义了递归案例。在这里，我们相信isBalanced返回正确的结果，只处理增量差异。这两条线处理：

case '('::tail => isBalanced(tail, count + 1) 
case ')'::tail => isBalanced(tail, count - 1) 

在每个，我们增加或减少相应的计数。最后一行（与case _::tail）处理所有其他情况，这不应该影响最终结果。

使用Scala强大的案例匹配功能（match），这非常简单。我们可以在比赛之前放置一名简单的后卫，以确保一旦平衡变为负值，我们就会早退。那么这是一个针对字符串输入的模式映射问题。这是远比使用无尽的if-else子句更清晰。

另请注意创建默认参数值的技巧，因此您无需通过0。这将澄清您的界面，同时允许您重新使用该功能。

为了证明正确性：

isBalanced("((()))".toList) // true 
isBalanced(")))(((".toList) // false 
isBalanced("(()())".toList) // true 
isBalanced("((()())".toList) // false 
isBalanced("Foo() bar()".toList) // true 

上打印日志行的注意事项：如果你需要这样做的情况下子句中微量的情况下映射是如何发生的，或做任意的体操，你可以这样做：

def isBalanced(string: List[Char], count: Int=0): Boolean = { 
    if (count < 0) { false } 
    else { 
    string match { 
     case Nil => count == 0 
     case '('::tail => { 
     println("Found an open paren") 
     isBalanced(tail, count + 1) 
     } 
     case ')'::tail => { 
     println("Found a close paren") 
     isBalanced(tail, count - 1) 
     } 
     case _::tail => isBalanced(tail, count) 
    } 
    } 
}