斯卡拉：确保牙套平衡

Question

我正在运行一个代码来平衡声明中的括号。我想我已经把它弄错了但是在一个特定的陈述上失败了，我需要理解为什么？

这是测试，特别是它失败了“（）”（“

不仅仅是编码，我认为我需要修复算法，任何指针？

def balance(chars: List[Char]): Boolean = {

  def find(c: Char, l: List[Char], i: Int): Int={
    if( l.isEmpty ) {
      if(c=='(')
        i+1
      else if(c==')')
        i-1
      else
        i
    }
    else if (c=='(')
      find(l.head, l.tail, i+1)
    else if(c==')')
      find(l.head,l.tail, i-1)
    else
      find(l.head,l.tail, i)

  }

  if(find(chars.head, chars.tail,0) ==0 )
     true
  else
     false

}


balance("())(".toList) //passes when it should fail
balance(":-)".toList)
balance("(if (zero? x) max (/ 1 x))".toList)
balance("I told him (that it's not (yet) done).\n(But he wasn't listening)".toList)

Answer 1

这是一个版本：

def balance(chars: List[Char]): Boolean = {
    def inner(c: List[Char], count: Int): Boolean = c match {
        case Nil                   => count == 0           // Line 1
        case ')' :: _ if count < 1 => false                // Line 2
        case ')' :: xs             => inner(xs, count - 1) // Line 3
        case '(' :: xs             => inner(xs, count + 1) // Line 4
        case _ :: xs               => inner(xs, count)     // Line 5
    }
    inner(chars, 0)
}

因此，在您的代码中，当您遇到正确的paranthesis时，我认为您错过了额外检查count <1！因此，如果检查'）'和count <1（上面的示例代码中的第2行），则需要额外的其他内容

Answer 2

你犯了一个非常简单且完全可以理解的错误。根据您目前的定义，)(中的括号是平衡的。只是他们不像我们通常想的那样平衡。在第一个字符之后，你有-1个未闭合的括号，然后在第二个字符后我们回到0，所以一切都很好。如果括号计数低于零，则括号不可能平衡。

现在有两种真正的方法可以解决这个问题。快速而肮脏的解决方案是抛出异常。

case object UnbalancedException extends Exception

if (i < 0)
  throw UnbalancedException

然后抓住它并在balance返回false。

try {
  ... // find() call goes in here
} catch {
  case UnbalancedException => false
}

功能更强大的解决方案是让find返回Option[Int]。在递归过程中，如果你得到None结果，那么返回None。否则，表现正常并返回Some(n)。如果您遇到i < 0然后返回None以指示失败的情况。然后在balance中，如果结果为非零或结果为None，则返回false。使用for表示法可以使这更漂亮，但如果你刚刚开始，那么手工编写它会非常有帮助。

Answer 3

您还可以使用Stack data structure的属性来解决此问题。当您看到开括号时，将其推入堆栈。当你看到关闭括号时，你从堆栈中弹出（而不是Stack我正在使用List，因为不可变的Stack is deprecated in Scala）：

def isBalanced(chars: Seq[Char]): Boolean = {
  import scala.annotation.tailrec

  case class BracketInfo(c: Char, idx: Int)
  def isOpen(c: Char): Boolean = c == '('
  def isClose(c: Char): Boolean = c == ')'
  def safePop[T](stack: List[T]): Option[T] = {
    if (stack.length <= 1) stack.headOption
    else stack.tail.headOption
  }

  @tailrec
  def isBalanced(chars: Seq[Char], idx: Int, stack: List[BracketInfo]): Boolean = {
    chars match {
      case Seq(c, tail@_*) =>
        val newStack = BracketInfo(c, idx) :: stack // Stack.push
        if (isOpen(c)) isBalanced(tail, idx + 1, newStack)
        else if (isClose(c)) {
          safePop(stack) match {
            case Some(b) => isBalanced(tail, idx + 1, stack.tail)
            case None =>
              println(s"Closed bracket '$c' at index $idx was not opened")
              false
          }
        }
        else isBalanced(tail, idx + 1, stack)
      case Seq() =>
        if (stack.nonEmpty) {
          println("Stack is not empty => there are non-closed brackets at positions: ")
          println(s"${stack.map(_.idx).mkString(" ")}")
        }
        stack.isEmpty
    }
  }

  isBalanced(chars, 0, List.empty[BracketInfo])
}