算法轉換爲Scala，看不出爲什麼它不起作用

Question

我正在編寫一些代碼來平衡括號，this question被證明對算法最有用。

我以我的第一語言（PHP）實現它，但我正在學習Scala並嘗試轉換代碼。

這是我的PHP代碼：

function balanced($string) { 
    return isBalanced($string, ""); 
} 

function isBalanced($chars, $stack) { 
    if (!strlen($chars)) 
    return empty($stack); 

    switch ($chars[0]) { 
    case '(': 
     // prepend stack with '(', move to next character 
     return isBalanced(substr($chars, 1), $chars[0] . $stack); 
    case ')': 
     // if '(' seen previously, shift stack, move to next character 
     return !empty($stack) && isBalanced(substr($chars, 1), substr($stack, 1)); 
    default: 
     // do nothing to stack, move to next character 
     return isBalanced(substr($chars, 1), $stack); 
    } 
} 

我已經測試這一點，它的工作原理。但是，當我將它轉換爲Scala時，它在平衡字符串上失敗。

我的Scala代碼：

object Main { 
    def balance(chars: List[Char]): Boolean = { 
    def balanced(chars: List[Char], stack: String): Boolean = { 
     if (chars.isEmpty) 
     stack.isEmpty 
     else if (chars.head == ')') 
     balanced(chars.tail, chars.head + stack) 
     else if (chars.head == '(') 
     !stack.isEmpty && balanced(chars.tail, stack.tail) 
     else 
     balanced(chars.tail, stack) 
    } 

    balanced(chars, "") 
    } 
} 

我明白這是不是最好的Scala代碼，但我剛剛開始。一些測試：

balance("(if (0) false (x))".toList) - fails 
balance("profit and loss (P&L).\n(cashflow)".toList) - fails 
balance(":)".toList) - passes 
balance(")(()".toList) - passes 

PHP等價物通過所有這些測試。我在我的Scala實現中做了什麼錯誤？

Answer 1

你已經混淆了(和)的情況。

Answer 2

對於它的價值，這裏有一個更地道Scala實現：

def balance(chars: List[Char]): Boolean = { 
    @tailrec def balanced(chars: List[Char], open: Int): Boolean = 
    chars match { 
     case  Nil => open == 0 
     case '(' :: t => balanced(t, open + 1) 
     case ')' :: t => open > 0 && balanced(t, open - 1) 
     case _ :: t => balanced(t, open) 
    } 

    balanced(chars, 0) 
} 

Answer 3

只是爲了保持完整性，我發現了一個更簡潔的「階式的」實現從another SO question：

def balance(chars: List[Char]): Boolean = chars.foldLeft(0){ 
    case (0, ')') => return false 
    case (x, ')') => x - 1 
    case (x, '(') => x + 1 
    case (x, _ ) => x 
} == 0 

Answer 4

它似乎我們正在參加相同的課程。我的解決方案：

def balance(chars: List[Char]): Boolean = 
doBalance(chars, 0) == 0; 
def doBalance(chars: List[Char], parenthesisOpenCount: Int): Int = 
if(parenthesisOpenCount <0) -100; 
else 
if(chars.isEmpty) parenthesisOpenCount 
else 
    chars.head match { 
    case '(' => return doBalance(chars.tail, parenthesisOpenCount+1) 
    case ')' => return doBalance(chars.tail, parenthesisOpenCount-1) 
    case _ => return doBalance(chars.tail, parenthesisOpenCount) 
} 

Answer 5

與Aaron Novstrup的答案相同，但使用'if else'。我也參加了同一門課程，但到目前爲止，我們只被教到了其他課程。

def balance(chars: List[Char]): Boolean = { 
    def balanced(chars: List[Char], open: Int): Boolean = 
     if (chars.isEmpty) open == 0 
     else if (chars.head == '(') balanced(chars.tail, open + 1) 
     else if (chars.head == ')') open > 0 && balanced(chars.tail, open - 1) 
     else balanced(chars.tail, open) 
    balanced(chars, 0) 
} 

Answer 6

我給這家

def balance(chars: List[Char]): Boolean = { 
var braceStack = new Stack[Char]() 

def scanItems(strList:List[Char]):Boolean = { 
    if(strList.isEmpty) 
     braceStack.isEmpty 
    else{ 
     var item = strList.head 
     item match { 
     case '(' => braceStack.push(item) 
        scanItems(strList.tail) 
     case ')'=> if(braceStack.isEmpty){ 
         false 
        } 
        else { 
         braceStack.pop 
         scanItems(strList.tail) 
        } 
     case _ => scanItems(strList.tail) 
     } 
    } 
} 

scanItems(chars) 

解決方案}

Answer 7

val myStack = new Stack[Char] 

    def balance(chars: List[Char]): Boolean = { 
    def processParanthesis(x: Char, a: List[Char]): Stack[Char] = { 
     if (x == '(') { 
     myStack.push('('); 
     } else if (x == ')') { 
     if (!myStack.empty()) 
      myStack.pop(); 
     else 
      myStack.push(')'); 
     } 
     if (a.length == 0) 
     return myStack; 
     else 
     return processParanthesis(a.head, a.tail); 
    } 
    return processParanthesis(chars.head, chars.tail).empty(); 
    } 

Answer 8

如果不使用開關的情況下，你可以使用遞歸來解決以高效的方式你的問題。

以下是我的代碼，實現與遞歸的幫助相同。您需要將字符串轉換爲我的方法的列表。

代碼：

object Balance { 

    def main(args: Array[String]): Unit = { 
    var paranthesis = "(234(3(2)s)d)" // Use your string here 
    println(bal(paranthesis.toList)) // converting the string to List 
    } 

    def bal(chars: List[Char]): Boolean ={ 
    // var check = 0 
    def fun(chars: List[Char],numOfOpenParan: Int): Boolean = { 
     if(chars.isEmpty){ 
     numOfOpenParan == 0 
     } 
     else{ 
     val h = chars.head 

     val n = 
      if(h == '(') numOfOpenParan + 1 
      else if (h == ')') numOfOpenParan - 1 
      else numOfOpenParan 

     // check = check + n 
     if (n >= 0) fun(chars.tail,n) 
     else false 
     } 
    } 
    fun(chars,0) 
    } 
}