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

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 2

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