pascal.sc

paren_balance.sc

package recfun

object session {

  // Balances parens...
  //
  def balance(chars: List[Char]): Boolean = {
  
  	import scala.annotation.tailrec
  
  	@tailrec
	def open(chars: List[Char], opened: Int): Boolean =
  		if (chars.isEmpty && opened == 0)
  			true
  		else if (chars.isEmpty && opened > 0)
  			false
  		else if (chars.head == ')')
  			if (opened > 0)
  				open(chars.tail, opened - 1)
  			else
  				false
  		else if (chars.head == '(')
  			open(chars.tail, opened + 1)
  		else
  			open(chars.tail, opened)

  	if (chars.isEmpty)
  		false
  	else
  		open(chars, 0)
  }                                               //> balance: (chars: List[Char])Boolean

  import org.scalatest.Assertions._
  assert(balance("(if (zero? x) max (/ 1 x))".toList))
  assert(!balance("".toList))
  assert(balance("()".toList))
  assert(balance("(())".toList))
  assert(balance("(())()".toList))
  assert(balance("((()()()))".toList))
  assert(balance("(())".toList))
  assert(balance("some text((more text) and more) and yet more".toList))
  assert(!balance(")some text((more text) and more) and yet more".toList))
  assert(!balance("some) text((more text) and more) and yet more".toList))
  assert(!balance("some( text((more text) and more) and yet more".toList))
  assert(!balance("some text((more text) and more)( and yet more".toList))
  assert(!balance("(()))".toList))
}