Given an expression string x. Examine whether the pairs and the orders of {,},(,),[,] are correct in exp.
For example, the function should return 'true' for exp = [()]{}{[()()]()} and 'false' for exp = [(]).
Note: The drive code prints "balanced" if function return true, otherwise it prints "not balanced".
Example 1:
Input:
{([])}
Output: 
true
Explanation: 
{ ( [ ] ) }. Same colored brackets can form 
balanced pairs, with 0 number of 
unbalanced bracket.
Example 2:
Input: 
()
Output: 
true
Explanation: 
(). Same bracket can form balanced pairs, 
and here only 1 type of bracket is 
present and in balanced way.
Example 3:
Input: 
([]
Output: 
false
Explanation: 
([]. Here square bracket is balanced but 
the small bracket is not balanced and 
Hence , the output will be unbalanced.
Your Task:
This is a function problem. You only need to complete the function ispar() that takes a string as a parameter and returns a boolean value true if brackets are balanced else returns false. The printing is done automatically by the driver code.
Expected Time Complexity: O(|x|)
Expected Auixilliary Space: O(|x|)
Constraints:
1 ≤ |x| ≤ 32000

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|x|)
Expected Auxiliary Space: O(|x|)

Starter code:
#User function Template for python3



class Solution:

    

    #Function to check if brackets are balanced or not.

    def ispar(self,x):

        # code here

Solutions:
class Solution:

	def ispar(self, x):
		open = ['{', '(', '[']
		close = ['}', ')', ']']
		stack = []
		for i in x:
			if i in open:
				stack.append(i)
			elif i in close:
				if len(stack) > 0:
					if close.index(i) == open.index(stack[-1]):
						stack.pop()
					else:
						return False
				else:
					return False
		return len(stack) == 0


class Solution:

	def __init__(self):
		self.stack1 = []

	def ispar(self, x):
		for i in range(len(x)):
			if not self.stack1:
				self.stack1.append(x[i])
			elif x[i] == ')' and self.stack1 and (self.stack1[-1] == '('):
				self.stack1.pop()
			elif x[i] == ']' and self.stack1 and (self.stack1[-1] == '['):
				self.stack1.pop()
			elif x[i] == '}' and self.stack1 and (self.stack1[-1] == '{'):
				self.stack1.pop()
			else:
				self.stack1.append(x[i])
		return not self.stack1


class Solution:

	def ispar(self, x):
		stack = []
		for p in x:
			if len(stack) == 0:
				stack.append(p)
			elif p == ')' and stack[-1] == '(':
				stack.pop()
			elif p == '}' and stack[-1] == '{':
				stack.pop()
			elif p == ']' and stack[-1] == '[':
				stack.pop()
			else:
				stack.append(p)
		if len(stack) == 0:
			return True
		return False


class Solution:

	def ispar(self, x):
		stack = []
		for ch in x:
			if ch == '(' or ch == '{' or ch == '[':
				stack.append(ch)
			else:
				if len(stack) == 0:
					return False
				top = stack.pop()
				if ch == ')' and top != '(':
					return False
				elif ch == '}' and top != '{':
					return False
				elif ch == ']' and top != '[':
					return False
		if len(stack) != 0:
			return False
		return True


class Solution:

	def ispar(self, x):
		stack = []
		for val in x:
			if val in {'(', '{', '['}:
				stack.append(val)
			else:
				if stack == []:
					return False
				poping = stack.pop()
				if val == ']' and poping != '[' or (val == '}' and poping != '{') or (val == ')' and poping != '('):
					return False
		return stack == []


parenthesis = {'{': '}', '(': ')', '[': ']'}

def is_left(p):
	return p in parenthesis.keys()

def is_right(p):
	return p in parenthesis.values()

class Solution:

	def ispar(self, arr):
		s = []
		for p in arr:
			if is_left(p):
				s.append(p)
			elif is_right(p):
				if len(s) == 0 or parenthesis[s.pop()] != p:
					return False
		if len(s) > 0:
			return False
		return True


class Solution:

	def ispar(self, x):
		l = []
		for i in x:
			if len(l) == 0:
				l.append(i)
			elif i == ')' and l[-1] == '(':
				l.pop()
			elif i == ']' and l[-1] == '[':
				l.pop()
			elif i == '}' and l[-1] == '{':
				l.pop()
			else:
				l.append(i)
		if len(l) == 0:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		while x:
			if '{}' in x:
				x = x.replace('{}', '')
			elif '()' in x:
				x = x.replace('()', '')
			elif '[]' in x:
				x = x.replace('[]', '')
			else:
				break
		return True if not x else False


import collections

class Solution:

	def ispar(self, x):
		stack = collections.deque()
		hmap = {'[': ']', '{': '}', '(': ')'}
		for i in range(len(x)):
			if len(stack) == 0:
				if x[i] in hmap:
					stack.append(x[i])
				else:
					return False
			elif x[i] in hmap:
				stack.append(x[i])
			elif hmap[stack.pop()] == x[i]:
				continue
			else:
				return False
		if len(stack) == 0:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		l = '{(['
		r = '})]'
		st = []
		for i in x:
			if i in l:
				st.append(i)
			elif len(st) == 0:
				return False
			elif l.find(st.pop()) != r.find(i):
				return False
		if len(st) != 0:
			return False
		else:
			return True


class Solution:

	def ispar(self, x):
		dic = {')': '(', ']': '[', '}': '{'}
		stack = []
		for ch in x:
			if ch not in dic:
				stack.append(ch)
			elif stack == [] or stack.pop() != dic[ch]:
				return False
		return stack == []


class Solution:

	def ispar(self, x):
		stack = []
		d = {'(': ')', '{': '}', '[': ']'}
		for i in x:
			if i in d:
				stack.append(i)
			elif stack == [] or d[stack.pop()] != i:
				return False
		return stack == []


class Solution:

	def ispar(self, x):
		stack = []
		opening = ['(', '[', '{']
		closing = [')', ']', '}']
		for char in x:
			if char in opening:
				stack.append(char)
			elif char in closing:
				if len(stack) == 0:
					return False
				top = stack.pop()
				if opening.index(top) != closing.index(char):
					return False
		return len(stack) == 0


class Solution:

	def ispar(self, x):
		stack = []
		mapDict = {'(': ')', '{': '}', '[': ']'}
		for elem in x:
			if elem in '([{':
				stack.append(elem)
			elif stack:
				openBracket = stack.pop()
				if mapDict[openBracket] != elem:
					return False
			else:
				return False
		return not stack


class Solution:

	def ispar(self, x):
		stack = []
		for i in x:
			if stack and i == ')' and (stack[-1] == '('):
				stack.pop()
			elif stack and i == '}' and (stack[-1] == '{'):
				stack.pop()
			elif stack and i == ']' and (stack[-1] == '['):
				stack.pop()
			else:
				stack.append(i)
		if stack:
			return False
		else:
			return True


class Solution:

	def ispar(self, x):
		stack = []
		opening_brackets = {'{', '[', '('}
		closing_brackets = {'}', ']', ')'}
		bracket_pairs = {'{': '}', '[': ']', '(': ')'}
		for char in x:
			if char in opening_brackets:
				stack.append(char)
			elif char in closing_brackets:
				if not stack:
					return False
				top = stack.pop()
				if bracket_pairs[top] != char:
					return False
		return len(stack) == 0


class Solution:

	def ispar(self, x):
		s = []
		for i in x:
			if i in ['(', '[', '{']:
				s.append(i)
			elif i in [')', ']', '}']:
				if not s:
					return False
				elif s[-1] == '(' and i == ')' or (s[-1] == '[' and i == ']') or (s[-1] == '{' and i == '}'):
					s.pop()
				else:
					return False
		if not s:
			return True
		return False


class Solution:

	def ispar(self, x):
		stack = []
		for i in x:
			if i in {'(', '[', '{'}:
				stack.append(i)
			elif stack == []:
				return False
			else:
				p = stack.pop()
				if p == '(' and i != ')' or (p == '[' and i != ']') or (p == '{' and i != '}'):
					return False
		return stack == []


class Solution:

	def ispar(self, x):
		lists = []
		open = ['{', '(', '[']
		close = ['}', ')', ']']
		for i in x:
			if i in open:
				lists.append(i)
			elif i in close:
				if len(lists) == 0:
					return False
				if open[close.index(i)] != lists.pop():
					return False
		return len(lists) == 0


class Solution:

	def ispar(self, x):
		stack = []
		n = len(x)
		hashmap = {'[': ']', '{': '}', '(': ')', '}': '', ']': '', ')': ''}
		if x[0] == ']' or x[0] == '}' or x[0] == ')':
			return False
		for i in range(n):
			if not stack or x[i] != hashmap[stack[-1]]:
				stack.append(x[i])
			else:
				stack.pop()
		if stack:
			return False
		else:
			return True


class Solution:

	def ispar(self, x):
		a = []
		for i in x:
			if i in ['(', '{', '[']:
				a.append(i)
			else:
				if not a:
					return False
				curr = a.pop()
				if curr == '(':
					if i != ')':
						return False
				if curr == '{':
					if i != '}':
						return False
				if curr == '[':
					if i != ']':
						return False
		if a:
			return False
		return True


class Solution:

	def ispar(self, x):
		stack = []
		opening_brackets = ['{', '(', '[']
		closing_brackets = ['}', ')', ']']
		bracket_map = {closing: opening for (opening, closing) in zip(opening_brackets, closing_brackets)}
		for char in x:
			if char in opening_brackets:
				stack.append(char)
			elif char in closing_brackets:
				if not stack:
					return False
				top = stack.pop()
				if top != bracket_map[char]:
					return False
		return len(stack) == 0


class Solution:

	def ispar(self, x):
		stk = []
		for br in x:
			if br in '[({':
				stk.append(br)
			else:
				if len(stk) == 0:
					return False
				prev = stk.pop()
				if prev == '(' and br == ')':
					continue
				elif prev == '{' and br == '}':
					continue
				elif prev == '[' and br == ']':
					continue
				else:
					return False
		if len(stk) == 0:
			return True
		return False


class Solution:

	def ispar(self, x):
		stack = []
		open_brackets = ['(', '[', '{']
		closing_brackets = [')', ']', '}']
		brackets_map = {')': '(', ']': '[', '}': '{'}
		for bracket in x:
			if bracket in open_brackets:
				stack.append(bracket)
			elif bracket in closing_brackets:
				if not stack or stack[-1] != brackets_map[bracket]:
					return False
				stack.pop()
		return len(stack) == 0


class Solution:

	def ispar(self, x):
		old_len = -1
		while old_len != len(x):
			old_len = len(x)
			x = x.replace('()', '')
			x = x.replace('{}', '')
			x = x.replace('[]', '')
		if len(x) == 0:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		stack = []
		opening_brackets = ['(', '{', '[']
		closing_brackets = [')', '}', ']']
		for char in s:
			if char in opening_brackets:
				stack.append(char)
			elif char in closing_brackets:
				if len(stack) == 0:
					return False
				opening_bracket = stack.pop()
				if opening_brackets.index(opening_bracket) != closing_brackets.index(char):
					return False
		return len(stack) == 0


class Solution:

	def ispar(self, arr):
		check = [arr[0]]
		for i in range(1, len(arr)):
			if arr[i] in ('{', '[', '('):
				check.append(arr[i])
			elif arr[i] == '}' and len(check) > 0 and (check[-1] == '{'):
				check.pop()
			elif arr[i] == ']' and len(check) > 0 and (check[-1] == '['):
				check.pop()
			elif arr[i] == ')' and len(check) > 0 and (check[-1] == '('):
				check.pop()
			else:
				return False
		if len(check) > 0:
			return False
		else:
			return True


class Solution:

	def ispar(self, x):
		mapping_par = {'{': '}', '(': ')', '[': ']'}
		stack = []
		for each in x:
			if each in ['{', '(', '[']:
				stack.append(each)
			elif each in ['}', ')', ']']:
				if stack and mapping_par[stack.pop()] == each:
					continue
				else:
					return False
			else:
				return False
		if stack:
			return False
		return True


class Solution:

	def ispar(self, x):
		stack = []
		flag = False
		for i in x:
			if i in ['{', '(', '[']:
				stack.append(i)
			else:
				if len(stack) == 0:
					return False
				current_char = stack.pop()
				if current_char == '{':
					if i != '}':
						return False
				elif current_char == '[':
					if i != ']':
						return False
				elif current_char == '(':
					if i != ')':
						return False
		if len(stack) == 0:
			return True


class Solution:

	def ispar(self, x):
		l = []
		if len(x) == 0 or len(x) == 1:
			return False
		l.append(x[0])
		for i in range(1, len(x)):
			if x[i] == '(' or x[i] == '[' or x[i] == '{':
				l.append(x[i])
			else:
				if len(l) == 0:
					return False
					break
				if x[i] == ')' and l[-1] == '(' or (x[i] == ']' and l[-1] == '[') or (x[i] == '}' and l[-1] == '{'):
					l.pop()
				else:
					l.append(x[i])
		if len(l) == 0:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		stack = []
		opening_bracket = ['(', '[', '{']
		closing_bracket = [')', ']', '}']
		for i in x:
			if i in opening_bracket:
				stack.append(i)
			elif i in closing_bracket:
				if not stack:
					return False
				top = stack.pop()
				if opening_bracket.index(top) != closing_bracket.index(i):
					return False
		return len(stack) == 0


class Solution:

	def ispar(self, x):
		stack = []
		pairs = {')': '(', '}': '{', ']': '['}
		for i in x:
			if i not in pairs:
				stack.append(i)
			elif stack == [] or stack[-1] != pairs[i]:
				return False
			else:
				stack.pop()
		return stack == []


class Solution:

	def ispar(self, x):
		stack = []
		for char in x:
			if char in ['{', '[', '(']:
				stack.append(char)
			else:
				if len(stack) == 0:
					return False
				if char == '}':
					if stack[-1] == '{':
						stack.pop()
						continue
				if char == ')':
					if stack[-1] == '(':
						stack.pop()
						continue
				if char == ']':
					if stack[-1] == '[':
						stack.pop()
						continue
				return False
		if len(stack):
			return False
		return True


class Solution:

	def ispar(self, x):
		stack = []
		openingChars = '({['
		closingChars = ')]}'
		char_pairs = {')': '(', '}': '{', ']': '['}
		for c in x:
			if c in openingChars:
				stack.append(c)
			elif c in closingChars:
				if not stack or stack[-1] != char_pairs[c]:
					return False
				stack.pop()
		return len(stack) == 0


class Solution:

	def ispar(self, x):
		stack = []
		for char in x:
			if char in ['(', '{', '[']:
				stack.append(char)
			else:
				if not stack:
					return False
				current_char = stack.pop()
				if current_char == '(':
					if char != ')':
						return False
				if current_char == '{':
					if char != '}':
						return False
				if current_char == '[':
					if char != ']':
						return False
		if stack:
			return False
		return True


from collections import deque

class Solution:

	def ispar(self, x):
		if len(s) <= 1:
			return False
		stack = deque()
		for i in s:
			if i in '({[':
				stack.append(i)
			elif len(stack) != 0 and stack[-1] == '(' and (i == ')'):
				stack.pop()
			elif len(stack) != 0 and stack[-1] == '{' and (i == '}'):
				stack.pop()
			elif len(stack) != 0 and stack[-1] == '[' and (i == ']'):
				stack.pop()
			else:
				return False
		return True if len(stack) == 0 else False


class Solution:

	def ispar(self, x):
		stack = []
		for i in x:
			if i in ['{', '[', '(']:
				stack.append(i)
			elif not stack:
				return False
			elif ismatch(stack[-1], i) == False:
				return False
			else:
				stack.pop()
		if stack:
			return False
		return True

def ismatch(a, b):
	if a == '{' and b == '}':
		return True
	elif a == '(' and b == ')':
		return True
	elif a == '[' and b == ']':
		return True
	else:
		return False


class Solution:

	def ispar(self, x):
		st = []
		for ch in x:
			if ch in ('[', '{', '('):
				st.append(ch)
			elif st and (st[-1] == '[' and ch == ']' or (st[-1] == '{' and ch == '}') or (st[-1] == '(' and ch == ')')):
				st.pop()
			else:
				return False
		return not st


class Solution:

	def ispar(self, x):
		openers = ['(', '[', '{']
		enders = [')', ']', '}']
		qu = []
		string = [*x]
		for c in string:
			if c in openers:
				qu.append(c)
			elif c in enders:
				if len(qu) == 0:
					return False
				idx = enders.index(c)
				if qu.pop() == openers[idx]:
					continue
				else:
					return False
			else:
				return False
		return not qu


class Solution:

	def ispar(self, s):
		dic = {'{': '}', '(': ')', '[': ']'}
		stack = []
		for elm in s:
			if elm in dic:
				stack.append(elm)
			elif len(stack) > 0 and dic[stack[-1]] == elm:
				stack.pop()
			else:
				return False
		if len(stack) == 0:
			return True
		return False


class Solution:

	def ispar(self, s):
		dic = {'{': '}', '(': ')', '[': ']'}
		stack = []
		for elm in s:
			if elm in dic or stack == []:
				stack.append(elm)
			elif stack[-1] in dic and elm == dic[stack[-1]]:
				stack.pop()
			else:
				return 0
		if stack == []:
			return 1
		return 0


class Solution:

	def ispar(self, x):
		mapping = {'(': ')', '[': ']', '{': '}'}
		stack = []
		for char in x:
			if char in mapping:
				stack.append(char)
			elif len(stack) == 0 or mapping[stack.pop()] != char:
				return
		False
		if len(stack) == 0:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		l = ['()', '[]', '{}']
		stack = []
		for i in x:
			if stack == []:
				stack.append(i)
			else:
				y = stack[-1] + i
				if y in l:
					stack.pop()
				else:
					stack.append(i)
		if stack == []:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		d = {'{': '}', '(': ')', '[': ']'}
		st = []
		for brac in x:
			if brac in d:
				st.append(brac)
			elif len(st) != 0 and d[st[-1]] == brac:
				st.pop()
			else:
				return False
		if len(st) == 0:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		while '()' in x or '[]' in x or '{}' in x:
			try:
				x = x.replace('()', '')
			except:
				pass
			try:
				x = x.replace('[]', '')
			except:
				pass
			try:
				x = x.replace('{}', '')
			except:
				pass
		if x == '':
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		brackets = {'}': '{', ']': '[', ')': '('}
		stack = []
		for i in s:
			if i in brackets:
				if stack and stack[-1] == brackets[i]:
					stack.pop()
				else:
					return False
			else:
				stack.append(i)
		return True if not stack else False


class Solution:

	def ispar(self, x):
		l = []
		for i in x:
			if i in ['{', '[', '(']:
				l.append(i)
			else:
				if l == []:
					return False
				if i == '}':
					if l[-1] == '{':
						l.pop()
						continue
				if i == ')':
					if l[-1] == '(':
						l.pop()
						continue
				if i == ']':
					if l[-1] == '[':
						l.pop()
						continue
				return False
		if len(l):
			return False
		return True


class Solution:

	def ispar(self, x):
		stack = []
		for c in x:
			if c in ['(', '{', '[']:
				stack.append(c)
			elif c in [')', '}', ']']:
				if not stack:
					return False
				if c == ')' and stack[-1] == '(':
					stack.pop()
				elif c == '}' and stack[-1] == '{':
					stack.pop()
				elif c == ']' and stack[-1] == '[':
					stack.pop()
				else:
					return False
		return not stack


class Solution:

	def ispar(self, x):
		st = []
		D = {'{': '}', '(': ')', '[': ']'}
		st.append(s[0])
		for v in s[1:]:
			if st:
				if st[-1] == '{' and v == '}':
					st.pop()
				elif st[-1] == '[' and v == ']':
					st.pop()
				elif st[-1] == '(' and v == ')':
					st.pop()
				else:
					st.append(v)
			else:
				st.append(v)
		if not st:
			return True
		else:
			return False


class Solution:

	def ispar(self, s):
		stack = []
		for c in s:
			if c == '(' or c == '{' or c == '[':
				stack.append(c)
			elif c == ')':
				if len(stack) < 1 or '(' != stack.pop():
					return False
			elif c == '}':
				if len(stack) < 1 or '{' != stack.pop():
					return False
			elif c == ']':
				if len(stack) < 1 or '[' != stack.pop():
					return False
		if stack:
			return False
		return True


class Solution:

	def ispar(self, x):
		mapping = {'(': ')', '[': ']', '{': '}'}
		st = []
		for i in x:
			if i in '[({':
				st.append(i)
			elif not st:
				return False
			else:
				if mapping[st[-1]] != i:
					return False
				st.pop()
		if st:
			return False
		return True


class Solution:

	def ispar(self, x):
		stack = []
		mapping = {')': '(', '}': '{', ']': '['}
		for char in x:
			if char in ['(', '{', '[']:
				stack.append(char)
			elif not stack or mapping[char] != stack.pop():
				return False
		return not stack


class Solution:

	def ispar(self, x):
		s = list(x)
		stk = []
		top = s[0]
		openn = ['(', '{', '[']
		close = [')', '}', ']']
		if top in close:
			return False
		for i in s:
			if i in openn:
				stk.append(i)
			else:
				if len(stk) == 0:
					return False
				top = stk.pop()
				if openn.index(top) != close.index(i):
					return False
		if len(stk) == 0:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		stack = []
		opening = '({['
		closing = ')}]'
		pair = {')': '(', '}': '{', ']': '['}
		for i in x:
			if i in opening:
				stack.append(i)
			if i in closing:
				if not stack:
					return False
				elif stack.pop() != pair[i]:
					return False
		if not stack:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		stack = []
		closeToOpen = {')': '(', '}': '{', ']': '['}
		for c in x:
			if c in closeToOpen:
				if stack and stack[-1] == closeToOpen[c]:
					stack.pop()
				else:
					return False
			else:
				stack.append(c)
		return True if len(stack) == 0 else False


class Solution:

	def ispar(self, x):
		while len(x) > 0:
			l = len(x)
			x = x.replace('()', '').replace('[]', '').replace('{}', '')
			if l == len(x):
				return False
		return True


class Solution:

	def ispar(self, x):
		max_num = 9999999999
		while max_num > len(x):
			max_num = len(x)
			x = x.replace('()', '')
			x = x.replace('{}', '')
			x = x.replace('[]', '')
		return not len(x) > 0


class Solution:

	def ispar(self, x):
		while '()' in x or '{}' in x or '[]' in x:
			x = x.replace('()', '').replace('[]', '').replace('{}', '')
		if len(x) == 0:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		stack = []
		if len(x) % 2:
			return False
		for char in x:
			if char in ('(', '{', '['):
				stack.append(char)
			else:
				if not stack:
					return False
				curr_char = stack.pop()
				if curr_char == '(':
					if char != ')':
						return False
				if curr_char == '[':
					if char != ']':
						return False
				if curr_char == '{':
					if char != '}':
						return False
		if stack:
			return False
		return True


class Solution:

	def ispar(self, x):
		l1 = []
		c = -1
		if len(s) == 1:
			return False
		for i in s:
			if i == '(' or i == '{' or i == '[':
				l1.append(i)
				c += 1
			elif i == ')' and len(l1) > 0:
				if l1[c] == '(':
					l1.pop()
					c -= 1
				else:
					l1.append(i)
					c += 1
			elif i == '}' and len(l1) > 0:
				if l1[c] == '{':
					l1.pop()
					c -= 1
				else:
					l1.append(i)
					c += 1
			elif i == ']' and len(l1) > 0:
				if l1[c] == '[':
					l1.pop()
					c -= 1
				else:
					l1.append(i)
					c += 1
			else:
				l1.append(i)
				c += 1
		if c == -1:
			return True
		else:
			return False


class Solution:

	def ispar(self, x):
		stack = []
		l = {')': '(', '}': '{', ']': '['}
		for p in x:
			if p in l.values():
				stack.append(p)
			elif stack and l[p] == stack[-1]:
				stack.pop()
			else:
				return False
		return stack == []


class Solution:

	def ispar(self, x):
		stack = []
		for char in x:
			if char in ['(', '[', '{']:
				stack.append(char)
			else:
				if not stack:
					return False
				top = stack.pop()
				if char == ')' and top != '(' or (char == ']' and top != '[') or (char == '}' and top != '{'):
					return False
		return len(stack) == 0


class Solution:

	def ispar(self, x):
		inp_list = []
		if x == '':
			return True
		open = ['(', '[', '{']
		dict = {'}': '{', ']': '[', ')': '('}
		if x[0] not in open:
			return False
		for i in x:
			if i in open:
				inp_list.append(i)
			else:
				try:
					if inp_list[-1] in open and dict[i] == inp_list[-1]:
						inp_list.pop()
					else:
						return False
				except:
					return False
		if len(inp_list) == 0:
			return True
		return False


class Solution:

	def ispar(self, x):
		list = []
		for i in range(len(x)):
			if len(list) == 0 and x[i] == '}' or (len(list) == 0 and x[i] == ']') or (len(list) == 0 and x[i] == ')'):
				return False
			if x[i] == '{' or x[i] == '[' or x[i] == '(':
				list.append(x[i])
			elif list[-1] == '{' and x[i] == '}' or (list[-1] == '[' and x[i] == ']') or (list[-1] == '(' and x[i] == ')'):
				list = list[:-1]
			else:
				return False
		if len(list) == 0:
			return True
		else:
			return False