Balanced Parentheses Check | Python

Problem : 

Given a string of opening and closing parentheses, 
check whether it’s balanced. 

We have 3 types of parentheses: round brackets: (), square brackets:
[], and curly brackets: {}. 

Assume that the string doesn’t contain 
any other character than these, no spaces words or numbers. 

As a reminder, balanced parentheses require every opening
parenthesis to be closed in the reverse order opened.
For example ‘([])’ is balanced but ‘([)]’ is not.

You can assume the input string has no spaces.

Solution :

def check_balanced_string(s1):
	
	if len(s1)%2 != 0:
		return False

	opening = set('([{')

	matches = set([ ('{','}'), ('[',']'), ('(',')') ])

	stack = []
	for perm in s1:

		if perm in opening:
			stack.append(perm)
		else:

			if len(stack) == 0 :
				return False
			last_val = stack.pop()

			if (last_val,perm) not in matches:
				return False

	return len(stack) == 0

# '([])'
b = check_balanced_string('[()]')
print b

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s