Given a string S, composed of different combinations of '(' , ')', '{', '}', '[', ']'. The task is to verify the validity of the arrangement.
An input string is valid if:
         1. Open brackets must be closed by the same type of brackets.
         2. Open brackets must be closed in the correct order.
Example 1:
Input:
S = ()[]{}
Output: 1
Explanation: The arrangement is valid.
 
Example 2:
Input:
S = ())({}
Output: 0
Explanation: Arrangement is not valid.
Example 3:
Input:
S = ([)]
Output: 0
Explanation: Arrangement is not valid.
 
Your Task:  
You dont need to read input or print anything. Complete the function valid() which takes S as input and returns a boolean value denoting whether the arrangement is valid or not.
Expected Time Complexity: O(N) where N is the length of S.
Expected Auxiliary Space: O(N) 
Constraints:
1 <= N <= 10^{4}

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N) where N is the length of S.
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:

    def valid(self, s): 

        #code here

Solutions:
class Solution:

	def valid(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 valid(self, s):
		stack = []
		for e in s:
			if len(stack) == 0 or e == '(' or e == '{' or (e == '['):
				stack.append(e)
			elif stack[-1] == '(' and e == ')':
				stack.pop()
			elif stack[-1] == '{' and e == '}':
				stack.pop()
			elif stack[-1] == '[' and e == ']':
				stack.pop()
			else:
				stack.append(e)
		return len(stack) <= 1


class Solution:

	def valid(self, s):
		mapping = {'{': 'c', '}': 'c', '(': 'b', ')': 'b', '[': 's', ']': 's'}
		btype = {}
		latest = []
		for bracket in s:
			if bracket in ('{', '[', '('):
				btype[mapping[bracket]] = btype.get(mapping[bracket], 0) + 1
				latest.append(mapping[bracket])
			if bracket in ('}', ']', ')'):
				btype[mapping[bracket]] = btype.get(mapping[bracket], 0) - 1
				if not len(latest):
					return 0
				if latest[-1] != mapping[bracket]:
					return 0
				latest.pop(-1)
			if btype[mapping[bracket]] < 0:
				return 0
		if len(latest):
			return 0
		return 1


class Solution:

	def valid(self, s):
		stack = []
		for i in range(len(s)):
			if s[i] == '(' or s[i] == '{' or s[i] == '[':
				stack.append(s[i])
			else:
				if len(stack) == 0:
					return False
				if stack[-1] == '(' and s[i] == ')' or (stack[-1] == '{' and s[i] == '}') or (stack[-1] == '[' and s[i] == ']'):
					stack.pop()
				else:
					return False
		return len(stack) == 0


class Solution:

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


class Solution:

	def valid(self, s):
		l = []
		for i in range(len(s)):
			if l == []:
				l.append(s[i])
			elif l != [] and l[-1] == '(' and (s[i] == ')'):
				l.pop()
			elif l != [] and l[-1] == '[' and (s[i] == ']'):
				l.pop()
			elif l != [] and l[-1] == '{' and (s[i] == '}'):
				l.pop()
			else:
				l.append(s[i])
		if len(l) == 0:
			return 1
		else:
			return 0


class Solution:

	def valid(self, s):
		tmp = []
		for i in s:
			if i == ')':
				if len(tmp) > 0:
					if tmp[-1] == '(':
						tmp.pop()
					else:
						tmp.append(i)
				else:
					tmp.append(i)
			elif i == '}':
				if len(tmp) > 0:
					if tmp[-1] == '{':
						tmp.pop()
					else:
						tmp.append(i)
				else:
					tmp.append(i)
			elif i == ']':
				if len(tmp) > 0:
					if tmp[-1] == '[':
						tmp.pop()
					else:
						tmp.append(i)
				else:
					tmp.append(i)
			else:
				tmp.append(i)
		if len(tmp) > 0:
			return False
		else:
			return True


class Solution:

	def valid(self, s):
		stck = []
		d = {'{': '}', '(': ')', '[': ']'}
		for i in s:
			if i in '{[(':
				stck.append(i)
			elif i in '}])':
				if not stck:
					return 0
				elif d[stck.pop()] == i:
					continue
				else:
					return 0
		if len(stck) > 0:
			return 0
		return 1


class Solution:

	def valid(self, s):
		mp = {')': '(', ']': '[', '}': '{'}
		stk = []
		for c in s:
			if c in mp:
				if not stk or stk[-1] != mp[c]:
					return False
				stk.pop()
			else:
				stk.append(c)
		return not stk


class Solution:

	def valid(self, s):
		st = []
		dic = {')': '(', '}': '{', ']': '['}
		for i in s:
			if i in [')', '}', ']']:
				if not st:
					return 0
				elif dic[i] == st[-1]:
					st.pop()
				else:
					return 0
			else:
				st.append(i)
		if not st:
			return 1
		return 0


class Solution:

	def valid(self, s):
		st = []
		for i in range(len(s)):
			if s[i] in ['(', '[', '{']:
				st.append(s[i])
			else:
				if len(st) == 0:
					return False
				check = st.pop()
				if s[i] == ')' and check != '(':
					return False
				if s[i] == ']' and check != '[':
					return False
				if s[i] == '}' and check != '{':
					return False
		if st:
			return False
		return True


class Solution:

	def valid(self, s):

		def check(b, a):
			if a == '[' and b == ']':
				return True
			elif a == '{' and b == '}':
				return True
			elif a == '(' and b == ')':
				return True
			return False
		stack = []
		for b in s:
			if b in ['[', '{', '(']:
				stack.append(b)
			elif not stack:
				return False
			elif check(b, stack[-1]):
				stack.pop()
			elif not check(b, stack[-1]):
				stack.append(b)
		if stack == []:
			return True
		return False


class Solution:

	def valid(self, s):
		stack = []
		for bracket in s:
			if bracket == '(' or bracket == '{' or bracket == '[':
				stack.append(bracket)
			else:
				if not stack:
					return False
				if bracket == ')' and stack[-1] != '(':
					return False
				if bracket == '}' and stack[-1] != '{':
					return False
				if bracket == ']' and stack[-1] != '[':
					return False
				stack.pop()
		if not stack:
			return True


class Solution:

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


class Solution:

	def valid(self, s):
		stack = []
		for i in s:
			if i in ['[', '{', '(']:
				stack.append(i)
			else:
				if not stack:
					return False
				cur = stack.pop()
				if cur == '{':
					if i != '}':
						return False
				if cur == '[':
					if i != ']':
						return False
				if cur == '(':
					if i != ')':
						return False
		if stack:
			return False
		return True


class Solution:

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


class Solution:

	def valid(self, s):
		e = []
		for i in s:
			if i == '}':
				if e == []:
					return 0
				p = e.pop()
				if p != '{':
					return 0
			elif i == ']':
				if e == []:
					return 0
				p = e.pop()
				if p != '[':
					return 0
			elif i == ')':
				if e == []:
					return 0
				p = e.pop()
				if p != '(':
					return 0
			else:
				e.append(i)
		if e != []:
			return 0
		return 1


class Solution:

	def valid(self, s):
		dic = {'(': ')', '{': '}', '[': ']'}
		dk = list(dic.keys())
		dv = list(dic.values())
		stack = []
		for c in s:
			if c in dk:
				stack.append(c)
			elif len(stack) == 0:
				ans = 0
				break
			elif c == dic[stack.pop()]:
				continue
			else:
				ans = 0
				break
		else:
			ans = 1
		if len(stack) != 0:
			ans = 0
		return ans


class Solution:

	def valid(self, s):
		stack = list()
		i = 0
		n = len(s)
		while i < n:
			top = len(stack) - 1
			if len(stack) == 0:
				if s[i] == ')' or s[i] == ']' or s[i] == '}':
					return False
				else:
					stack.append(s[i])
			elif s[i] == ')':
				if stack[top] == '(':
					stack.pop()
				else:
					stack.append(s[i])
			elif s[i] == ']':
				if stack[top] == '[':
					stack.pop()
				else:
					stack.append(s[i])
			elif s[i] == '}':
				if stack[top] == '{':
					stack.pop()
				else:
					stack.append(s[i])
			else:
				stack.append(s[i])
			i += 1
		if len(stack) == 0:
			return True
		else:
			return False


class Solution:

	def valid(self, s):
		S = []
		for char in s:
			if char in '({[':
				S.append(char)
			elif char is ')':
				if not S or S[-1] != '(':
					return False
				S.pop()
			elif char is '}':
				if not S or S[-1] != '{':
					return False
				S.pop()
			elif char is ']':
				if not S or S[-1] != '[':
					return False
				S.pop()
		if not S:
			return True
		return False


class Solution:

	def valid(self, s):
		st = []
		st.append(s[0])
		for i in range(1, len(s)):
			if len(st) > 0 and (s[i] == ')' or s[i] == ']' or s[i] == '}'):
				x = s[i]
				if x == ')' and st[-1] == '(':
					st.pop()
					continue
				elif x == '}' and st[-1] == '{':
					st.pop()
					continue
				elif x == ']' and st[-1] == '[':
					st.pop()
					continue
				else:
					return 0
			elif s[i] == '(' or s[i] == '[' or s[i] == '{':
				st.append(s[i])
				continue
			elif len(st) == 0 and (s[i] == ')' or s[i] == ']' or s[i] == '}'):
				return 0
		if len(st) > 0:
			return 0
		else:
			return 1


class Solution:

	def valid(self, s):
		st = []
		opening = ['(', '{', '[']
		closing = [')', '}', ']']
		for i in s:
			if i in opening:
				st.append(i)
			else:
				a = i
				indexi = closing.index(a)
				while len(st) != 0 and st[len(st) - 1] != opening[indexi]:
					st.pop()
				if len(st) == 0:
					return 0
				else:
					st.pop()
		if len(st) == 0:
			return 1
		return 0


class Solution:

	def valid(self, s):
		c = 0
		tt = ['(', '{', '[']
		kk = [')', '}', ']']
		st = []
		d = {')': '(', '}': '{', ']': '['}
		for i in range(len(s)):
			if s[i] in tt:
				c = c + 1
				st.append(s[i])
			elif s[i] in kk:
				if len(st) == 0:
					return 0
				if st[-1] == d[s[i]]:
					st.pop()
					c = c - 1
		if c == 0:
			return 1
		else:
			return 0


class Solution:

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


class Solution:

	def valid(self, s):
		map = {']': '[', '}': '{', ')': '('}
		stack = []
		for char in s:
			if char in map:
				recent = stack.pop() if stack else '#'
				if recent != map[char]:
					return False
			else:
				stack.append(char)
		return not stack


class Solution:

	def valid(self, s):
		a = []
		i = 0
		while i < len(s):
			if '(' == s[i] or '{' == s[i] or '[' == s[i]:
				a.append(s[i])
			elif a == []:
				return 0
			elif s[i] == ')' and a[-1] == '(':
				a.pop()
			elif s[i] == '}' and a[-1] == '{':
				a.pop()
			elif s[i] == ']' and a[-1] == '[':
				a.pop()
			else:
				return 0
			i = i + 1
		if a == []:
			return 1
		return 0


class Solution:

	def valid(self, s):
		stack = []
		opp = {']': '[', ')': '(', '}': '{'}
		for x in s:
			if x in '[({':
				stack.append(x)
			else:
				if not stack:
					return False
				if stack[-1] == opp[x]:
					stack.pop()
				else:
					return False
		return not stack


class Solution:

	def valid(self, s):
		arr = []
		for i in s:
			if i in ['[', '{', '(']:
				arr.append(i)
			else:
				if arr == []:
					return False
				current_i = arr[len(arr) - 1]
				arr.pop(len(arr) - 1)
				if current_i == '(':
					if i != ')':
						return False
				if current_i == '{':
					if i != '}':
						return False
				if current_i == '[':
					if i != ']':
						return False
		if arr == []:
			return True
		else:
			return False


class Solution:

	def valid(self, s):
		stack = []
		for i in s:
			if i in ['(', '{', '[']:
				stack.append(i)
			else:
				if not stack:
					return 0
				i1 = stack.pop()
				if i1 == '(':
					if i != ')':
						return 0
				if i1 == '{':
					if i != '}':
						return 0
				if i1 == '[':
					if i != ']':
						return 0
		if stack:
			return 0
		else:
			return 1


class Solution:

	def valid(self, s):
		stack = []
		st1 = []
		st2 = []
		n = len(s)
		for i in range(len(s)):
			if s[i] == '[' or s[i] == '(' or (s[i] == '{' and i != n - 1):
				st1.append(s[i])
			if s[i] == ']' or s[i] == ')' or (s[i] == '}' and i != 0):
				st2.append(s[i])
		if len(st1) != len(st2):
			return 0
		for c in s:
			if c in '({[':
				stack.append(c)
			elif c in ')}]':
				if not stack:
					return 0
				if c == ')' and stack[-1] == '(' or (c == '}' and stack[-1] == '{') or (c == ']' and stack[-1] == '['):
					stack.pop()
				else:
					return 0
		return 1


class Solution:

	def correct(self, p1, p2):
		return p1 == '(' and p2 == ')' or (p1 == '[' and p2 == ']') or (p1 == '{' and p2 == '}')

	def valid(self, s):
		st = []
		for p in s:
			if p in '([{':
				st.append(p)
			elif st == []:
				return False
			elif not self.correct(st.pop(), p):
				return False
		return st == []


class Solution:

	def valid(self, S):
		dic = {'(': ')', '[': ']', '{': '}'}
		stack = []
		for elm in S:
			if elm in dic:
				stack.append(elm)
			elif len(stack) == 0:
				return 0
			else:
				val = stack.pop()
				if dic[val] != elm:
					return 0
		if len(stack) > 0:
			return 0
		return 1


class Solution:

	def valid(self, s):
		d = {')': '(', ']': '[', '}': '{'}
		st = []
		for i in s:
			if i not in d:
				st.append(i)
			else:
				if len(st) == 0:
					return False
				top = st[-1]
				if top == d[i]:
					st.pop()
				else:
					return False
		else:
			if len(st) == 0:
				return True
			else:
				return False


class Solution:

	def valid(self, s):
		stack = []
		key = 0
		for i in s:
			if i != '}' and i != ']' and (i != ')'):
				stack.insert(key, i)
				key += 1
			else:
				if key == 0:
					return False
				if stack[key - 1] == '(' and i == ')':
					stack.pop(key - 1)
					key -= 1
				elif stack[key - 1] == '[' and i == ']':
					stack.pop(key - 1)
					key -= 1
				elif stack[key - 1] == '{' and i == '}':
					stack.pop(key - 1)
					key -= 1
				else:
					return False
		if stack == []:
			return True
		else:
			return False


class Solution:

	def valid(self, s):
		ob = []
		d = {'(': ')', '{': '}', '[': ']'}
		l = 0
		for i in s:
			if i == '(' or i == '{' or i == '[':
				ob.append(i)
				l += 1
			elif len(ob) != 0:
				t = ob.pop()
				if d[t] == i:
					continue
				else:
					return False
		if len(ob) == 0:
			return True
		else:
			return False


class Solution:

	def valid(self, s):
		c = dict(('()', '[]', '{}'))
		stack = []
		for i in s:
			if i in '([{':
				stack.append(i)
			elif len(stack) == 0 or i != c[stack.pop()]:
				return 0
		return len(stack) == 0


class Solution:

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


class Solution:

	def valid(self, s):

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


class Solution:

	def valid(self, s):
		dic1 = {'}': '{', ']': '[', ')': '('}
		stack = []
		for i in s:
			if i in '[({':
				stack.append(i)
			elif stack:
				if dic1[i] == stack[-1]:
					stack.pop()
				else:
					return 0
			else:
				return 0
		return 1 if len(stack) == 0 else 0


class Solution:

	def valid(self, s):
		dic = {'(': ')', '{': '}', '[': ']'}
		keys = list(dic.keys())
		values = list(dic.values())
		stack = []
		for i in s:
			if i in dic:
				stack.append(i)
			else:
				pos = values.index(i)
				if not stack or keys[pos] != stack.pop():
					return 0
		if stack:
			return 0
		return 1


class Solution:

	def isOpeningParanthesis(self, p):
		if p in ('(', '{', '['):
			return True
		else:
			return False

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

	def valid(self, s):
		if s == '':
			return 1
		stack = []
		for paranthesis in s:
			if self.isOpeningParanthesis(paranthesis):
				stack.append(paranthesis)
			else:
				try:
					if not self.matchParanthesis(stack.pop(), paranthesis):
						return 0
				except:
					return 0
		if len(stack) == 0:
			return 1
		return 0


class Solution:

	def valid(self, s):
		st = []
		open = ['(', '[', '{']
		close = [')', ']', '}']
		for i in s:
			if i in open:
				st.append(i)
			elif len(st) == 0:
				return 0
			else:
				op = st.pop()
				if open.index(op) != close.index(i):
					return 0
		if len(st) == 0:
			return 1
		return 0


class Solution:

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


class Solution:

	def valid(self, s):
		sulut = '{[('
		stack = []
		for item in s:
			if item in sulut:
				stack.append(item)
			elif not stack:
				return False
			elif item == ')' and stack[-1] == '(':
				stack.pop()
			elif item == ']' and stack[-1] == '[':
				stack.pop()
			elif item == '}' and stack[-1] == '{':
				stack.pop()
			else:
				return False
		return False if stack else True


class Solution:

	def valid(self, s):
		l = list(s)
		x = []
		for i in range(len(l)):
			if len(x) == 0:
				if l[i] == ')' or l[i] == '}' or l[i] == ']':
					return 0
			if l[i] == '(' or l[i] == '{' or l[i] == '[':
				x.append(l[i])
			elif l[i] == ')':
				if x[-1] == '(':
					x.pop()
			elif l[i] == ']':
				if x[-1] == '[':
					x.pop()
			elif l[i] == '}':
				if x[-1] == '{':
					x.pop()
		if len(x) == 0:
			return 1
		else:
			return 0


class Solution:

	def valid(self, s):
		stack = []
		for curr_char in s:
			if curr_char == '(' or curr_char == '{' or curr_char == '[':
				stack.append(curr_char)
			else:
				if len(stack) == 0:
					return False
				if curr_char == ')' and stack[-1] != '(':
					return False
				if curr_char == '}' and stack[-1] != '{':
					return False
				if curr_char == ']' and stack[-1] != '[':
					return False
				stack.pop()
		if len(stack) == 0:
			return True
		else:
			return False


class Solution:

	def valid(self, s):
		r = [s[0]]
		n = len(s)
		for i in range(1, n):
			if s[i] in ['(', '{', '[']:
				r.append(s[i])
			else:
				if r == []:
					return False
				if s[i] == ')':
					if r[-1] != '(':
						return False
					r.pop()
				if s[i] == '}':
					if r[-1] != '{':
						return False
					r.pop()
				if s[i] == ']':
					if r[-1] != '[':
						return False
					r.pop()
		if r != []:
			return False
		return True


class Solution:

	def valid(self, s):
		stack = []
		d = {')': '(', '}': '{', ']': '['}
		for ch in s:
			if ch in d:
				if stack and d[ch] == stack[-1]:
					stack.pop()
				else:
					return 0
			elif ch in '({[':
				stack.append(ch)
		return 0 if stack else 1


class Solution:

	def isOpenBracket(self, c):
		if c == '[' or c == '{' or c == '(':
			return True
		return False

	def check(self, openBracket, closeBracket):
		match = {'(': 1, '[': 2, '{': 3, ')': -1, ']': -2, '}': -3}
		check = match[openBracket] + match[closeBracket]
		return check == 0

	def valid(self, s):
		arr = []
		for c in s:
			if self.isOpenBracket(c):
				arr.append(c)
			elif len(arr) > 0 and self.check(c, arr[-1]) == True:
				arr.pop()
			else:
				return False
		if len(arr) > 0:
			return False
		return True


class Solution:

	def __init__(self):
		self.stack = []
		self.top = -1

	def push(self, val):
		self.top += 1
		self.stack.append(val)

	def pop(self):
		if self.top == -1:
			return ''
		val = self.stack.pop(self.top)
		self.top -= 1
		return val

	def valid(self, s):
		d = {'{': '}', '[': ']', '(': ')'}
		for i in s:
			if i == '{' or i == '[' or i == '(':
				self.push(d[i])
			else:
				val = self.pop()
				if val != i:
					return 0
		if self.top == -1:
			return 1
		else:
			return 0


class Solution:

	def valid(self, s):
		open = ['(', '{', '[']
		close = [')', '}', ']']
		temp = []
		for i in s:
			if i in open:
				temp.append(i)
			elif i in close:
				try:
					if temp[-1] == open[close.index(i)]:
						temp.pop()
					else:
						return 0
				except:
					return 0
		if len(temp) != 0:
			return 0
		return 1


class Solution:

	def valid(self, s):
		temp = []
		i = 0
		while i < len(s):
			if s[i] == '(' or s[i] == '{' or s[i] == '[':
				temp.append(s[i])
			if s[i] in ['}', ')', ']']:
				if len(temp) == 0:
					return False
					break
				if s[i] == '}' and temp[len(temp) - 1] == '{':
					del temp[len(temp) - 1]
				elif s[i] == ']' and temp[len(temp) - 1] == '[':
					del temp[len(temp) - 1]
				elif s[i] == ')' and temp[len(temp) - 1] == '(':
					del temp[len(temp) - 1]
				else:
					temp.append(s[i])
			i += 1
		if len(temp) == 0:
			return True
		else:
			return False


class Solution:

	def valid(self, s):
		if len(s) == 1:
			return False
		if len(s) > 1:
			l = []
			v = []
			c = 0
			for i in range(len(s)):
				if s[i] == '[' or s[i] == '{' or s[i] == '(':
					l.append(s[i])
				if len(l) > 0:
					if s[i] == ']' and l[-1] == '[':
						l.pop()
					elif s[i] == '}' and l[-1] == '{':
						l.pop()
					elif s[i] == ')' and l[-1] == '(':
						l.pop()
					elif s[i] == ']' and l[-1] != '[':
						v.append(s[i])
					elif s[i] == '}' and l[-1] != '{':
						v.append(s[i])
					elif s[i] == '}' and l[-1] != '(':
						v.append(s[i])
				else:
					return False
			if len(l) == 0 and len(v) == 0:
				return True
			elif len(l) > 0 or len(v) > 0:
				return False
			if c > 0:
				return False


class Solution:

	def valid(self, a):
		n = '({['
		s = []
		if len(a) % 2 != 0:
			return 0
		for i in range(len(a)):
			if a[i] in n:
				s.append(a[i])
			elif len(s) == 0:
				return 0
			elif a[i] == ')' and s[-1] == '(' or (a[i] == '}' and s[-1] == '{') or (a[i] == ']' and s[-1] == '['):
				s.pop()
			else:
				return 0
		else:
			if len(s) == 0:
				return 1
			return 0


class Solution:

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


class Solution:

	def valid(self, s):
		l = []
		for char in s:
			if char in ['(', '{', '[']:
				l.append(char)
			else:
				if not l:
					return False
				ch = l.pop()
				if ch == '(':
					if char != ')':
						return False
				if ch == '{':
					if char != '}':
						return False
				if ch == '[':
					if char != ']':
						return False
		if l:
			return False
		return True


class Solution:

	def valid(self, s):
		x = []
		for i in s:
			if i in '({[':
				x.append(i)
			elif i is ')':
				if not x or x[-1] != '(':
					return 0
				x.pop()
			elif i is '}':
				if not x or x[-1] != '{':
					return 0
				x.pop()
			elif i is ']':
				if not x or x[-1] != '[':
					return 0
				x.pop()
		if not x:
			return 1
		return 0


class Solution:

	def valid(self, s):
		open = ['(', '{', '[']
		close = {')': '(', '}': '{', ']': '['}
		stack = []
		for c in s:
			if c in open:
				stack.append(c)
			elif len(stack) == 0 or stack[-1] != close[c]:
				return 0
			else:
				stack.pop()
		if len(stack) == 0:
			return 1
		return 0


class Solution:

	def valid(self, s):
		q = []
		d = {}
		d['('] = ')'
		d['{'] = '}'
		d['['] = ']'
		opening = ['(', '{', '[']
		for i in s:
			if i in opening:
				q.append(i)
			elif q:
				temp = q.pop()
				if d[temp] == i:
					continue
				else:
					return False
			else:
				fl = 1
				return False
		if q:
			return False
		return True


class Solution:

	def valid(self, s):
		closetoopne = {')': '(', '}': '{', ']': '['}
		stack = []
		for elem in s:
			if elem in closetoopne:
				if stack and stack[-1] == closetoopne[elem]:
					stack.pop()
				else:
					return 0
			else:
				stack.append(elem)
		return 1 if len(stack) == 0 else 0


class Solution:

	def valid(self, s):
		stack = []
		for item in s:
			if item == '(' or item == '{' or item == '[':
				stack.append(item)
			elif len(stack) == 0:
				return 0
			else:
				ele = stack[len(stack) - 1]
				if not (item == ')' and ele == '(' or (item == '}' and ele == '{') or (item == ']' and ele == '[')):
					return 0
				else:
					stack.pop()
		return 1 if len(stack) == 0 else 0