How to balance parenthesis recursively

Question

I'm working on some code to balance parenthesis, this question proved most useful for the algorithm.

I implemented it in my first language (PHP) but I'm 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've test this, it works. However, when I convert it to Scala, it fails on balanced strings.

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 this isn't the best Scala code but I'm just starting out. 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

The PHP equivalent passes all these tests. What have I done wrong in my Scala implementation?

Answer 1

Adding to Vigneshwaran's answer (including comments & filtering unnecessary letters to avoid extra recursive calls):

def balance(chars: List[Char]): Boolean = {
  @scala.annotation.tailrec
  def recurs_balance(chars: List[Char], openings: Int): Boolean = {
    if (chars.isEmpty) openings == 0
    else if (chars.head == '(') recurs_balance(chars.tail, openings + 1)
    else openings > 0 && recurs_balance(chars.tail, openings - 1)
  }

  recurs_balance(chars.filter(x => x == '(' || x == ')'), 0)
}

Answer 2

Instead of using Switch case you can use recursion to solve your problem in an efficient way.

Following is my code to achieve the same with the help of 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 3

  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 4

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 5

Same as Aaron Novstrup's answer but using 'if else'. I'm also attending the same course but we are taught upto if/else only 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 6

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

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 7

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

For what it's worth, here's a more idiomatic Scala implementation:

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 9

You have mixed up the cases for ( and ).