Algorithm converted to Scala cannot understand why it does not work

Question

I am working on some code for balancing brackets, this question turned out to be the most useful for the algorithm.

I implemented it in my first language (PHP), but I am learning Scala and trying to convert the code.

Here is my PHP code:

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

I tested this, it works. However, when I convert it to Scala, it does not work on balanced lines.

My Scala code:

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

I appreciate that this is not the best Scala code, but I'm just getting started. Some tests:

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

. All of these tests pass the equivalent of PHP. What have I done wrong in my Scala implementation?

Answer 1

You have messed up the cases for ( ) .

Answer 2

For what it's worth, here's a more idiomatic implementation of 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

Just for completeness, I found an even more complex implementation of <scala -esque 'from 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

Same as Aaron Noststrup, but using 'if else'. I also attend the same course, but we are only taught upto if / else so far.

 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 5

Instead of using a switch, you can use recursion to efficiently solve your problem.

Below is my code to achieve the same result using recursion. You need to convert the string to List for my method.

Code:

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

Answer 6

My solution for this

 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

It seems we are attending the same course. my decision:

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