balanced_parentheses.py

def balance_recurse(chars, cnt=0):
	if len(chars) == 0: return cnt == 0
	if chars[0] == '(': cnt += 1
	if chars[0] == ')': cnt -= 1
	return cnt >= 0 and balance(chars[1:], cnt)

PARENS = (('(', ')'), ('[', ']'),)
def balance_recurse_mul(chars, cnt=[0]*len(PARENS)):
	if len(chars) == 0: return all(map(lambda b: b==0, cnt))
	for i, paren in enumerate(PARENS):
		if chars[0] == paren[0]: cnt[i] += 1
		if chars[0] == paren[1]: cnt[i] -= 1
	return all(map(lambda b: b>=0, cnt)) and balance_recurse_mul(chars[1:], cnt)


def balance(chars):
	def f(cnt, c):
		if cnt >= 0: 
			if c == '(': cnt += 1
			if c == ')': cnt -= 1
		return cnt
	return 0 == reduce(lambda cnt, c: f(cnt, c), chars, 0)




def balance_bal(chars):
	print chars
	if chars.find('(') >= 0:
		return balance_right(chars[chars.index('(')+1:])
	if chars.find(')') >= 0:
		return False
	return True

def balance_right(chars):
	if chars.find('(') >= 0:
		return balance_bal(chars) and balance_right(chars[chars.index(')')+1:])
	if chars.find(')') >= 0:
		return True
	return False



import unittest
class Test(unittest.TestCase):
	def test(self):
		self.assertTrue(balance(''))
		self.assertTrue(balance('x'))
		self.assertFalse(balance('('))
		self.assertFalse(balance(')'))
		self.assertTrue(balance('()'))
		self.assertTrue(balance('(if(zero?x)max(/ 1 x))'))
		self.assertTrue(balance('I told him (that not (yet)done).(but he)'))
		self.assertFalse(balance(':-)'))
		self.assertFalse(balance('())('))		

	def test3(self):
		# self.assertTrue(balance_bal(''))
		# self.assertTrue(balance_bal('x'))
		# self.assertFalse(balance_bal('('))
		# self.assertFalse(balance_bal(')'))
		# self.assertTrue(balance_bal('()'))
		# self.assertTrue(balance_bal('(if(zero?x)max(/ 1 x))'))
		self.assertTrue(balance_bal('I told him (that not (yet)done).(but he)'))
		# self.assertFalse(balance_bal(':-)'))
		# self.assertFalse(balance_bal('())('))		

	def test2(self):
		self.assertTrue(balance_recurse_mul(''))
		self.assertTrue(balance_recurse_mul('x'))
		# self.assertFalse(balance_recurse_mul('('))
		# self.assertFalse(balance_recurse_mul(')'))
		self.assertTrue(balance_recurse_mul('()'))
		self.assertTrue(balance_recurse_mul('(if(zero?x)max(/ 1 x))'))
		self.assertTrue(balance_recurse_mul('I told him (that not (yet)done).(but he)'))
		self.assertFalse(balance_recurse_mul(':-)'))
		self.assertFalse(balance_recurse_mul('())('))		


if __name__ == '__main__':
	unittest.main()