Scala:确保大括号是平衡的

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)
}

因此，在您的代码中，当您遇到正确的括号时，我认为您缺少对 count < 1 的额外检查!因此，如果同时检查 ')' 和 count < 1(上面示例代码中的第 2 行)，则您需要一个额外的 else