0

簡単な括弧のバランシング関数を書こうとしているときに、scala が if ステートメントを評価する方法がわからないことを知りました。

def balance(chars: List[Char]): Boolean = {
  def loop(chars: List[Char], opened: Int): Boolean = {
    println(opened)
    println(chars.head)
    if (opened < 0) return false
    if (chars.isEmpty && opened == 0) return true
    if (chars.isEmpty && opened > 0) return false
    if (!chars.isEmpty && chars.head.toString == "(") loop(chars.tail, opened+1)
    if (!chars.isEmpty && chars.head.toString == ")") loop(chars.tail, opened-1)
    else loop(chars.tail, opened)
  }
loop(chars, 0)
}

これを実行すると、3 回目の反復までに、println(opened) が表示され、opened = -1 が要求されます。(opened < 0) ----> (-1 < 0) -----> true と想像したので、false を返します。そうではありません - なぜですか？

4

1 に答える 1

2

Scalaifは、宣言された順序で式を評価します。このアルゴリズムの問​​題は、else他の条件が真でない場合にのみ最後の式が評価されると想定していることですifが、入力 '(X))' を使用すると、2 つの再帰ツリーが作成されます。1 つは条件用で!chars.isEmpty && chars.head.toString == "("、もう1 つはelse loop(chars.tail, opened)です。これは、=-1 を開いたときに再帰が終了していないという印象を与えますが、実際に表示されているのは「else」再帰ツリーです。

解決？あなたはちょうど欠けていelseます：

if (!chars.isEmpty && chars.head.toString == "(") loop(chars.tail, opened+1) **else**

(注: このコードはおそらくmatch...caseステートメントを使用して改善できます。これにより、前のelse問題が発生するのを防ぐことができます。また、文字と文字を比較できます。それらを文字列に変換する必要はありません: chars.head.toString == "("=> chars.head == '(')

*編集* コメントの後、リスト構造でパターンマッチングを使用する方法は次のとおりです。

def loop(chars: List[Char], opened: Int): Boolean = {
    if (opened < 0) return false else 
    chars match {
    case Nil => opened == 0
    case '('::tail => loop(tail, opened + 1)
    case ')'::tail => loop(tail, opened -1)
    case x::tail => loop(tail, opened)
}

これが役立つことを願っています。

于 2013-09-26T22:43:22.043 に答える