Scala：中括弧のバランスがとれていることを確認してください

Question

私はステートメントの角括弧のバランスをとるコードを実行しています。私はそれが正しいと思うが、それは1つの特定のステートメントで失敗している、私はなぜ理解する必要がありますか？

これは、それは私がアルゴを修正する必要があると思うコーディング、任意のポインタ？

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が発生したときに、カウント< 1のための追加のチェックが欠落していると思うので、それがBOをチェックする場合は、他の追加を必要とします！ （上記の例のコードの2行目）

Answer 2

あなたは非常に単純で完全に理解できる間違いをしました。 )(のカッコは、現在の定義によってバランスが取れています。それは、私たちが通常考えている方法でバランスがとれていないということだけです。最初の文字の後には、閉じられていないカッコがあり、2番目の文字の後に0に戻っているので、すべて正常です。 かっこの数がゼロ以下になると、かっこは平衡することはできません。

これを処理する2つの本当の方法があります。迅速で汚れた解決策は、例外をスローすることです。

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で、結果が0以外の場合またはの場合、結果はNone、falseを返します。これはforという表記でよりきれいにすることができますが、それを始めるのであれば手で書くことが非常に役立ちます。

Answer 3

Stack data structureのプロパティを使用して、この問題を解決することもできます。開きブラケットが見えるときは、スタックに押し込みます。あなたは閉じ括弧が表示されたら、あなたはスタックからポップ（スタックではなく、私はリストを使用しています、なぜなら不変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]) 
}