我正在用scala进行函数式编程，并且在尝试编写递归方法来查找平衡括号时有点困惑。
免责声明 - 我不是在寻找复制/粘贴答案，我只是希望有人能指出为什么我的条件语句没有评估(我对 scala 很陌生，所以条件本身就是表达式的想法对我来说是一个新概念)。
这是我到目前为止的尝试：
def balance(chars: List[Char]): Boolean = {
val charStack = new Stack[Char]()
def balanceRec(chars: List[Char]): Boolean = {
if (chars.isEmpty) charStack.isEmpty
println(chars.mkString(", "))
if (chars.head == ')' &&
charStack.isEmpty
) {
false
}
else if (chars.head == ')' &&
charStack.pop() != '('
) {
false
}
else{
if(chars.head == '(') charStack.push(chars.head)
balanceRec(chars.tail)
}
}
balanceRec(chars)
}
我正在测试一个非常简单的输入，例如val chars = List('(', 't', 'e', 's', 't', ')', 'a')，甚至仍然得到一个java.util.NoSuchElementException: head of empty list.
我很困惑为什么我的第二个else if声明没有开火返回false.此外，我已经充实了这些条件，以确保我理解它们像我认为的那样工作 - 请不要取笑我:)
让我们从清理一下开始，以便更容易地了解正在发生的事情。
错误显然在balanceRec范围内，所以我们甚至不需要查看balance：
def balanceRec(chars: List[Char]): Boolean = {
if (chars.isEmpty) charStack.isEmpty
println(chars.mkString(", "))
if (chars.head == ')' &&
charStack.isEmpty
) {
false
}
else if (chars.head == ')' &&
charStack.pop() != '('
) {
false
}
else{
if(chars.head == '(') charStack.push(chars.head)
balanceRec(chars.tail)
}
}
接下来，println显然也不是问题的一部分，所以让我们删除它：
def balanceRec(chars: List[Char]): Boolean = {
if (chars.isEmpty) charStack.isEmpty
if (chars.head == ')' &&
charStack.isEmpty
) {
false
}
else if (chars.head == ')' &&
charStack.pop() != '('
) {
false
}
else{
if(chars.head == '(') charStack.push(chars.head)
balanceRec(chars.tail)
}
}
此外，让我们删除一些不必要的括号并清理空格和缩进：
def balanceRec(chars: List[Char]): Boolean = {
if (chars.isEmpty) charStack.isEmpty
if (chars.head == ')' && charStack.isEmpty) false
else if (chars.head == ')' && charStack.pop() != '(') false
else {
if (chars.head == '(') charStack.push(chars.head)
balanceRec(chars.tail)
}
}
现在，该方法的结构变得更加清晰。
我们现在注意到，第一个表达式是 NO-OP：它没有副作用，它不会改变任何东西，它不会打印任何东西，它的结果没有返回，它的结果没有打印，它的结果没有分配给变量或字段。它实际上什么都不做。
这是主要问题。
事实证明，我们需要做的就是在第二个if之前插入一个else关键字：
def balanceRec(chars: List[Char]): Boolean = {
if (chars.isEmpty) charStack.isEmpty
else if (chars.head == ')' && charStack.isEmpty) false
else if (chars.head == ')' && charStack.pop() != '(') false
else {
if (chars.head == '(') charStack.push(chars.head)
balanceRec(chars.tail)
}
}
[斯卡斯蒂链接]
由于我们方法的主体现在是单个表达式，我们可以去掉大括号：
def balanceRec(chars: List[Char]): Boolean =
if (chars.isEmpty) charStack.isEmpty
else if (chars.head == ')' && charStack.isEmpty) false
else if (chars.head == ')' && charStack.pop() != '(') false
else {
if (chars.head == '(') charStack.push(chars.head)
balanceRec(chars.tail)
}
最后，一些一般提示。
你实际上并没有在代码中使用List的任何特定功能，你只是在使用Seq更通用的功能，事实上，你实际上只是在使用Iterable的功能。我更喜欢保持我的接口尽可能通用和通用，所以我将这里的类型更改为Iterable：
def balance(chars: Iterable[Char]): Boolean = {
val charStack = new Stack[Char]()
def balanceRec(chars: Iterable[Char]): Boolean =
if (chars.isEmpty) charStack.isEmpty
else if (chars.head == ')' && charStack.isEmpty) false
else if (chars.head == ')' && charStack.pop() != '(') false
else {
if (chars.head == '(') charStack.push(chars.head)
balanceRec(chars.tail)
}
balanceRec(chars)
}
接下来，我发现使用该方法很尴尬，因为我必须传入单个字符的集合，而我发现传入字符串更自然：
def balance(s: String): Boolean = {
val charStack = new Stack[Char]()
def balanceRec(chars: Iterable[Char]): Boolean =
if (chars.isEmpty) charStack.isEmpty
else if (chars.head == ')' && charStack.isEmpty) false
else if (chars.head == ')' && charStack.pop() != '(') false
else {
if (chars.head == '(') charStack.push(chars.head)
balanceRec(chars.tail)
}
balanceRec(s.toIterable)
}
但实际上，String也支持head和tail，所以这里没有必要使用Iterable：
def balance(s: String): Boolean = {
val charStack = new Stack[Char]()
def balanceRec(s: String): Boolean =
if (s.isEmpty) charStack.isEmpty
else if (s.head == ')' && charStack.isEmpty) false
else if (s.head == ')' && charStack.pop() != '(') false
else {
if (s.head == '(') charStack.push(s.head)
balanceRec(s.tail)
}
balanceRec(s)
}
我也更喜欢使用工厂方法而不是构造函数，所以我会像这样初始化堆栈：
val charStack = Stack.empty[Char]
在函数式编程中，与许多其他社区不同，只要代码仍然可读，短变量名是完全可以接受的。此外，我们通常信任我们的类型，因此，例如，您不必说charStack：我们知道它是一个堆栈，因为它具有类型Stack！命名事物集合的典型命名模式是附加一个s来表示复数形式，因此我们可以表示这个chars，甚至只是cs(作为一个快乐的巧合，也可以读作"char stack"的缩写)。
def balance(s: String): Boolean = {
val cs = Stack.empty[Char]
def balanceRec(s: String): Boolean =
if (s.isEmpty) cs.isEmpty
else if (s.head == ')' && cs.isEmpty) false
else if (s.head == ')' && cs.pop() != '(') false
else {
if (s.head == '(') cs.push(s.head)
balanceRec(s.tail)
}
balanceRec(s)
}
现在我们已经大大缩短了代码，我们注意到第二和第三个备选方案(前两个else)具有相同的结果：它们都计算为false。因此，我们可以简单地将他们的条件与 OR 联系起来：
def balance(s: String): Boolean = {
val cs = Stack.empty[Char]
def balanceRec(s: String): Boolean =
if (s.isEmpty) cs.isEmpty
else if (s.head == ')' && cs.isEmpty || s.head == ')' && cs.pop() != '(') false
else {
if (s.head == '(') cs.push(s.head)
balanceRec(s.tail)
}
balanceRec(s)
}
现在我们可以应用一些布尔代数并分解出s.head =='('条件：
def balance(s: String): Boolean = {
val cs = collection.mutable.Stack.empty[Char]
def balanceRec(s: String): Boolean =
if (s.isEmpty) cs.isEmpty
else if (s.head == ')' && (cs.isEmpty || cs.pop() != '(')) false
else {
if (s.head == '(') cs.push(s.head)
balanceRec(s.tail)
}
balanceRec(s)
}
最后，不需要一个可变的累加器在不同的递归调用之间传递信息，因为该语言已经为我们提供了允许我们将信息传入和传出调用的工具：参数和返回值！
因此，我们可以简单地将一个不可变的堆栈(我们只是为此使用List)作为参数传递，并将其作为值返回，而不是将状态信息保存在可变堆栈中：
def balance(s: String): Boolean = {
def balanceRec(s: String, cs: List[Char] = Nil): (Boolean, List[Char]) =
if (s.isEmpty) (cs.isEmpty, cs)
else if (s.head == ')' && cs.isEmpty || s.head == ')' && cs.head != '(') (false, cs)
else balanceRec(s.tail, if (s.head == '(') s.head :: cs else cs)
balanceRec(s)._1
}
请注意，与我上面所说的不同，我们在这里使用List[Char]而不是Seq[Char]、Iterable[Char]或String，因为在这种情况下，我们确实使用了List的一个特征，即O(1)前置，头和尾，其他三个都不能保证。
!!另请注意，此代码是错误的!!
我们没有解释您的原始代码使用副作用的事实，更准确地说，突变。例如，第二个分支，即使没有被采用，仍可能导致pop()ping 堆栈的顶部元素。让我再说一遍：一个没有被采取的分支会改变结果。
特别是，如果s.head == ')'是true的，cs.isEmpty是false的，cs.head != '('是false的(换句话说，cs.head == '('是true的)，那么我们pop()最顶层的元素，即使我们不采用这个分支，这种突变在if/else链的后面分支以及未来的递归调用中仍然可见。
因此，我们必须以与最终else中类似的方式考虑这一点：
def balance(s: String): Boolean = {
def balanceRec(s: String, cs: List[Char] = Nil): (Boolean, List[Char]) =
if (s.isEmpty) (cs.isEmpty, cs)
else if (s.head == ')' && cs.isEmpty) (false, cs)
else if (s.head == ')' && cs.head != '(') (false, cs.tail)
else if (s.head == ')' && cs.head == '(') balanceRec(s.tail, if (s.head == '(') s.head :: cs.tail else cs.tail)
else balanceRec(s.tail, if (s.head == '(') s.head :: cs else cs)
balanceRec(s)._1
}
现在，你可能会看到这个，然后说："我认为函数式编程应该如此简单和美丽，但我在这里看到的是，当我们把可变解决方案转换为不可变解决方案时，它变成了三重嵌套逻辑的复杂混乱"。但事情是这样的：可变版本有完全相同的混乱！您只是没有看到它，因为通过可变堆栈连接的代码的不同部分之间的依赖关系是不可见的。但他们仍然在那里。
作为替代解决方案，请注意，我们实际上根本不需要知道堆栈的内容。我们只需要知道堆栈有多深！因此，我们可以改为执行以下操作：
def balance(s: String): Boolean = {
def balanceRec(cs: List[Char], depth: Int = 0): Int =
if (depth < 0) depth
else cs match {
case Nil => depth
case '(' :: cs => balanceRec(cs, depth + 1)
case ')' :: cs => balanceRec(cs, depth - 1)
case c :: cs => balanceRec(cs, depth)
}
balanceRec(s.toList) == 0
}
我只想指出，递归并不总是需要的，有时递归并不是做某事的最实用的方式。
如果我们只想确定括号是否平衡，我们只想知道是否有相同数量的(和).
编辑：这忘记了考虑到)(会返回 true，尽管它是无效的！我已经更新了响应以说明这一点。
为了解决这个问题，我们可以考虑到运行总计必须始终大于零
我们可以使用map将Char列表转换为Int列表
我们可以把一个(变成一个+1，一个)变成一个-1，以及所有其他我们不关心的角色，并可以把他们变成0
为了检查余额，我们的新列表的总和应该是0的，并且该值永远不会低于零
为了实现这一点，我们可以使用foldLeft运算符，它需要两个参数列表
val testList: List[Char] = List('(', 't', 'e', 's', 't', 'i', 'n', 'g', ')', '!')
val mappedList: List[Int] = testList.map{ currentChar =>
if (currentChar == '(') 1
else if (currentChar == ')') -1
else 0
}
def foldOp(currentTotal: Int, newValue: Int) = {
if (currentTotal < 0) {
currentTotal
} else {
currentTotal + newValue
}
}
val initialValue: Int = 0
val sumResult: Int = mappedList.foldLeft(initialValue)(foldOp)
val isBalanced: Boolean = sumResult == 0
// true
作为一个函数，这可能看起来像这样：
def isBalanced( charList: List[Char] ): Boolean = {
def mapChar( char: Char): Int = {
if (char == '(') 1
else if (char == ')') -1
else 0
}
def foldOp(currentTotal: Int, newValue: Int) = {
if (currentTotal < 0) {
currentTotal
} else {
currentTotal + newValue
}
}
val charToIntList: List[Int] = charList.map(mapChar)
val sum: Int = charToIntList.foldLeft(0)(foldOp)
sum == 0
}
模式匹配也是一个很好的功能工具：
def isBalanced( charList: List[Char] ): Boolean = {
charList.map{
case '(' => 1
case ')' => -1
case _ => 0
}.foldLeft(0)(foldOp) == 0
}
我在这里的目标不是为您提供应该复制/粘贴的答案，而是想分享我自己的方法和解释，以表达对此类问题的解决方案。我的目标是希望激发解决方案，或者窥探解决问题的许多不同方法。
现在，话虽如此，这绝对可以递归完成：
def isBalanced( charList: List[Char], runningTotal: Int = 0 ): Boolean = {
if (runningTotal < 0) {
false
}
charList match {
// Base Case (1) Empty List, return whether or not the total is 0
case Nil => runningTotal == 0
// Recursive Case head char and the rest of the list
case headChar :: rest =>
val mappedValue: Int = headChar match {
case '(' => 1
case ')' => -1
case _ => 0
}
isBalanced(rest, runningTotal + mappedValue)
}
}
最后，我还想指出filter。对于小列表，这是一种相当冗长的做事方式，但如果列表非常大，这将减少要检查的元素的大小(可能更适合更复杂的用例)
正如 Luis 指出的那样，collect这样做要好得多，它将像 map 一样应用部分函数(匹配)[_ match { case ... }的语法糖]，但对于任何未定义的情况，它都不会被收集。
def isBalanced( charList: List[Char] ): Boolean = {
val mappedValues: List[Int] = charList.collect{
case '(' => 1
case ')' => -1
}
mappedValues.foldLeft(initialValue)(foldOp)
}