括號平衡算法

Question

我正在使用scala中的一個小程序來檢查某些表達式i是否相對於括號的打開和關閉正確形成。這是問題here但我自己的程序。

def balance(chars: List[Char]): Boolean = { 
    def balanced(chars: List[Char], opened: Int, closed: Int): Boolean = { 
    if (chars.isEmpty && opened == closed) true 
    else if (opened < closed) false 
    else { 
    if (chars.head == '(') balanced(chars.tail, opened + 1, closed) 
    if (chars.head == ')') balanced(chars.tail, opened, closed + 1) 
    else balanced(chars.tail, opened, closed) 
    } 
} 
    balanced(chars, 0, 0) 

}

的println（平衡（ 「只是（有些（隨機）的句子）。\ n（即不工作）」。toList））

的問題是，例如它不適用於這個例子。我追溯了程序，當我們從遞歸調用返回時，顯然問題出現了，但我無法弄清楚錯誤是什麼。

Answer 1

在

else { 
    if (chars.head == '(') balanced(chars.tail, opened + 1, closed) 
    if (chars.head == ')') balanced(chars.tail, opened, closed + 1) 
    else balanced(chars.tail, opened, closed) 
} 

你有兩個獨立的if表達，當你想將它們視爲一個單一的情況下表達。如果chars.head == '('是true遞歸調用作出，但結果被忽略，而第二if進行評估。氏s將導致else分支被採用，這有效地忽略了在第一個表達式中找到的(。您可以使用例如match

chars match { 
    case Nil => opened == closed 
    case '('::cs => balanced(cs, opened + 1, closed) 
    case ')'::cs => balanced(cs, opened, closed + 1) 
    case _::cs => balanced(cs, opened, closed) 
} 

Answer 2

你可以試試下面的代碼可在上面的例子中它爲你的工作也有問題，如果你有「SSS）FFF（」它也給真正所以將錯就錯在邏輯上

def balance(chars: List[Char]): Boolean = { 
    def balrec(chars: List[Char], accr: Int, accl: Int): Boolean = { 
     chars match { 
     case head :: tail => 
      if (head.equals('(')) balrec(tail, accr + 1, accl) 
      else if (head.equals(')') && (accr > accl || accr == 0)) balrec(tail, accr, accl + 1) 
      else balrec(tail, accr, accl) 
     case Nil => if (accr == accl) true else false 
     } 
    } 

    balrec(chars, 0, 0) 
    }