A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. 

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

It contains no unmatched brackets.
The subset of brackets enclosed within the confines of a matched pair of brackets  is also a matched pair of brackets.

Given $n$ strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES.  Otherwise, return NO.  

Function Description  

Complete the function isBalanced in the editor below.   

isBalanced has the following parameter(s):

string s: a string of brackets   

Returns   

string: either YES or NO  

Input Format

The first line contains a single integer $n$, the number of strings. 

Each of the next $n$ lines contains a single string $s$, a sequence of brackets.

Constraints

$1\leq n\leq10^3$  
$1\leq|s|\leq10^3$, where $|s|$ is the length of the sequence.  
All chracters in the sequences ∈ { {, }, (, ), [, ] }.

Output Format

For each string, return YES or NO.

Sample Input
STDIN           Function
-----           --------
3               n = 3
{[()]}          first s = '{[()]}'
{[(])}          second s = '{[(])}'
{{[[(())]]}}    third s ='{{[[(())]]}}'

Sample Output
YES
NO
YES

Explanation

The string {[()]} meets both criteria for being a balanced string. 
The string {[(])} is not balanced because the brackets enclosed by the matched pair { and } are not balanced: [(]).      
The string {{[[(())]]}} meets both criteria for being a balanced string.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
def check():
	stack = []
	s = input()
	for c in s:
		if c == '(':
			stack.append(0)
		elif c == ')':
			if len(stack) > 0 and stack[-1] == 0:
				stack.pop()
			else:
				return -1
		elif c == '[':
			stack.append(2)
		elif c == ']':
			if len(stack) > 0 and stack[-1] == 2:
				stack.pop()
			else:
				return -1
		if c == '{':
			stack.append(4)
		elif c == '}':
			if len(stack) > 0 and stack[-1] == 4:
				stack.pop()
			else:
				return -1
	if len(stack) == 0:
		return 0
	else:
		return -1

def solve():
	t = int(input())
	for i in range(0, t):
		if check() == 0:
			print('YES')
		else:
			print('NO')
solve()


class Stack:

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

	def push(self, val):
		self.arr.append(val)

	def pop(self):
		size = len(self.arr)
		if size > 0:
			popval = self.arr[size - 1]
			self.arr.pop()
			return popval
		else:
			return ''

	def size(self):
		return len(self.arr)

def eval(line):
	dic = {'(': ')', '{': '}', '[': ']', '': ''}
	mystack = Stack()
	strlen = len(line)
	for x in range(0, strlen):
		ch = line[x]
		if ch == '{' or ch == '[' or ch == '(':
			mystack.push(ch)
		else:
			popval = mystack.pop()
			if dic[popval] != ch:
				return 'NO'
	if mystack.size() == 0:
		return 'YES'
	else:
		return 'NO'
no_testcases = int(input())
if no_testcases > 1000:
	no_testcases = 1000
testcases = []
for x in range(no_testcases):
	line = input()
	if len(line) > 1000:
		cut_part = 1000 - len(line)
		line = line[:cut_part]
	testcases.append(line)
for x in range(no_testcases):
	line = testcases[x]
	ret = eval(line)
	print(ret)


def checkParenthesis(line):
	list = []
	for i in range(len(line)):
		if line[i] == '{' or line[i] == '(' or line[i] == '[':
			list.append(line[i])
		if line[i] == '}':
			if len(list) == 0:
				print('NO')
				return
			popped = list.pop()
			if popped != '{':
				print('NO')
				return
		if line[i] == ')':
			if len(list) == 0:
				print('NO')
				return
			popped = list.pop()
			if popped != '(':
				print('NO')
				return
		if line[i] == ']':
			if len(list) == 0:
				print('NO')
				return
			popped = list.pop()
			if popped != '[':
				print('NO')
				return
	if len(list) != 0:
		print('NO')
		return
	print('YES')
n = int(input())
while n != 0:
	n -= 1
	line = input()
	checkParenthesis(line)


t = int(input())
while t:
	ar = ['e']
	s = input()
	for i in s:
		if i == '(':
			ar.append('(')
		elif i == '[':
			ar.append('[')
		elif i == '{':
			ar.append('{')
		elif i == ')':
			k = ar.pop()
			if k != '(':
				ar.append('k')
				break
		elif i == ']':
			k = ar.pop()
			if k != '[':
				ar.append('k')
				break
		elif i == '}':
			k = ar.pop()
			if k != '{':
				ar.append('k')
				break
	if len(ar) == 0 or ar[len(ar) - 1] != 'e':
		print('NO')
	else:
		print('YES')
	t -= 1


import sys
t = int(input().strip())
for i in range(t):
	line = input().strip()
	stack = []
	for ch in line:
		if ch in '})]':
			try:
				top = stack.pop()
				if top == '{' and ch != '}' or (top == '(' and ch != ')') or (top == '[' and ch != ']'):
					print('NO')
					break
			except:
				print('NO')
				break
		else:
			stack.append(ch)
	else:
		if stack:
			print('NO')
		else:
			print('YES')


T = int(input())
while T != 0:
	s = input()
	l = len(s)
	f = 0
	stack = []
	for i in s:
		if i == '(' or i == '{' or i == '[':
			stack.append(i)
		try:
			if i == ')' and stack[-1] == '(':
				f += 1
				stack.pop()
			elif i == '}' and stack[-1] == '{':
				f += 1
				stack.pop()
			elif i == ']' and stack[-1] == '[':
				f += 1
				stack.pop()
		except IndexError:
			continue
	if f == l / 2 and l % 2 == 0:
		print('YES')
		T -= 1
	else:
		print('NO')
		T -= 1


def calculate(parentheses):
	opened = ['(', '{', '[']
	pairs = [('(', ')'), ('{', '}'), ('[', ']')]
	stack = []
	for i in parentheses:
		if i in opened:
			stack.append(i)
		else:
			if not stack:
				return False
			if (stack.pop(), i) not in pairs:
				return False
	if stack:
		return False
	return True

def actions():
	while True:
		yield input()
go = actions()
N = int(next(go))
for i in range(N):
	print('YES' if calculate(next(go)) else 'NO')


o = '{[('
c = '}])'
for _ in range(int(input())):
	s = []
	for e in input():
		if e in o:
			s.append(e)
		elif not len(s) or c[o.index(s.pop())] != e:
			print('NO')
			break
	else:
		if len(s):
			print('NO')
		else:
			print('YES')


n = int(input())
i = 0
open = ['{', '[', '(']
close = ['}', ']', ')']
while i < n:
	line = input()
	p = []
	balanced = True
	for x in line:
		if x not in close:
			p.append(x)
		else:
			if len(p) == 0:
				balanced = False
				break
			prev = p.pop()
			if x == '}' and prev != '{':
				balanced = False
				break
			elif x == ']' and prev != '[':
				balanced = False
				break
			elif x == ')' and prev != '(':
				balanced = False
				break
	if len(p) == 0 and balanced:
		print('YES')
	else:
		print('NO')
	i += 1


import sys

class Stack:

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

	def push(self, arg):
		self.list.append(arg)

	def pop(self):
		return self.list.pop()

	def size(self):
		return len(self.list)

	def isEmpty(self):
		return len(self.list) == 0

def check_parentheses(param):
	s = Stack()
	is_balanced = True
	index = 0
	while index < len(param) and is_balanced:
		symbol = param[index]
		if symbol in '({[':
			s.push(symbol)
		elif s.isEmpty():
			is_balanced = False
		else:
			top = s.pop()
			if not matched(top, symbol):
				is_balanced = False
		index += 1
	if s.isEmpty() and is_balanced:
		return 'YES'
	else:
		return 'NO'

def matched(opens, close):
	opened = '({['
	closer = ')}]'
	return opened.index(opens) == closer.index(close)
n = int(input())
i = 0
while i < n:
	x = input()
	print(check_parentheses(x))
	i += 1


n = int(input().strip())

def isCorrectBraces(br):
	stk = []
	for ch in val:
		if ch in ('{', '(', '['):
			stk.append(ch)
		elif ch == '}':
			if len(stk) == 0 or stk.pop() != '{':
				return False
		elif ch == ')':
			if len(stk) == 0 or stk.pop() != '(':
				return False
		elif len(stk) == 0 or stk.pop() != '[':
			return False
	return len(stk) == 0
for i in range(n):
	val = input().strip()
	print('YES' if isCorrectBraces(val) else 'NO')


n = int(input())
strings = []
while n > 0:
	strings.append(input())
	n -= 1

def check_balanced(string):
	s = []
	try:
		for p in list(string):
			if p in ['(', '{', '[']:
				s.append(p)
			elif p == ')':
				if s.pop() != '(':
					return False
			elif p == ']':
				if s.pop() != '[':
					return False
			elif p == '}':
				if s.pop() != '{':
					return False
	except IndexError:
		return False
	return len(s) == 0
for string in strings:
	print('YES' if check_balanced(string) else 'NO')


N = int(input())
for n in range(N):
	line = input()
	balance = []
	try:
		for l in line:
			if l in '({[':
				balance.append(l)
			elif l in ')}]':
				x = balance.pop()
				if l == ')' and x != '(':
					raise IndexError
				elif l == '}' and x != '{':
					raise IndexError
				elif l == ']' and x != '[':
					raise IndexError
		if len(balance) == 0:
			print('YES')
		else:
			print('NO')
	except IndexError:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	b = []
	T = True
	for j in range(l):
		if s[j] == '{' or s[j] == '(' or s[j] == '[':
			b.append(s[j])
		elif s[j] == '}':
			if len(b) == 0:
				print('NO')
				T = False
				break
			elif b[-1] == '{':
				b.pop()
			else:
				print('NO')
				T = False
				break
		elif s[j] == ')':
			if len(b) == 0:
				print('NO')
				T = False
				break
			elif b[-1] == '(':
				b.pop()
			else:
				print('NO')
				T = False
				break
		elif len(b) == 0:
			print('NO')
			T = False
			break
		elif b[-1] == '[':
			b.pop()
		else:
			print('NO')
			T = False
			break
	if T == True and len(b) == 0:
		print('YES')
	elif T == True and len(b) != 0:
		print('NO')


def balanced(t):
	li = []
	for item in t:
		if item == '[' or item == '{' or item == '(':
			li.append(item)
		elif item == ']':
			if len(li) == 0 or li[-1] != '[':
				return False
				break
			else:
				del li[-1]
		elif item == ')':
			if len(li) == 0 or li[-1] != '(':
				return False
				break
			else:
				del li[-1]
		elif item == '}':
			if len(li) == 0 or li[-1] != '{':
				return False
				break
			else:
				del li[-1]
	return len(li) == 0
a = int(input())
result = ''
for i in range(a):
	t = input()
	if balanced(t):
		result += 'YES'
	else:
		result += 'NO'
	if i != a - 1:
		result += '\n'
print(result)


def is_balanced(s):
	p = []
	m = {'}': '{', ']': '[', ')': '('}
	for c in s:
		if c in '{[(':
			p.append(c)
			continue
		if p and m[c] == p.pop():
			continue
		else:
			return 'NO'
	if p:
		return 'NO'
	return 'YES'
for _ in range(int(input())):
	print(is_balanced(input()))


n = int(input())
for _ in range(0, n):
	stack = []
	braces = list(input())
	balanced = True
	for brace in braces:
		if brace == '(' or brace == '{' or brace == '[':
			stack.append(brace)
		elif len(stack) > 0:
			top = stack[len(stack) - 1]
			if top == '(' and brace == ')' or (top == '[' and brace == ']') or (top == '{' and brace == '}'):
				stack.pop()
			else:
				balanced = False
				break
		else:
			balanced = False
			break
	if balanced and len(stack) == 0:
		print('YES')
	else:
		print('NO')


_OPENING_BRACKETS = ['{', '(', '[']
_CLOSING_BRACKETS = ['}', ')', ']']

def is_seq_correct(seq):
	if len(seq) % 2:
		return False
	opening_seq = list()
	it = 0
	for x in seq:
		if x in _OPENING_BRACKETS:
			opening_seq.append(_OPENING_BRACKETS.index(x))
		elif x in _CLOSING_BRACKETS:
			if len(opening_seq) == 0 or opening_seq[-1] != _CLOSING_BRACKETS.index(x):
				return False
			opening_seq.pop()
		it += 1
	return opening_seq == list()
test_cases = int(input())
while test_cases > 0:
	line = input()
	if is_seq_correct(line):
		print('YES')
	else:
		print('NO')
	test_cases -= 1


match = {'(': ')', '[': ']', '{': '}'}
for _ in range(int(input())):
	passes = True
	stack = list()
	for c in input():
		if c in '([{':
			stack.append(c)
		elif stack and match[stack[-1]] == c:
			stack.pop()
		else:
			passes = False
			break
	print('YES' if passes and (not stack) else 'NO')


o = ['{', '[', '(']
c = ['}', ']', ')']
t = int(input())
for i in range(t):
	s = input()
	b = True
	a = []
	for j in range(len(s)):
		if s[j] in o:
			a.append(s[j])
		elif len(a) > 0 and o.index(a[len(a) - 1]) == c.index(s[j]):
			del a[len(a) - 1]
		else:
			b = False
			break
	if b and len(a) == 0:
		print('YES')
	else:
		print('NO')


def opposite(c):
	if c == ')':
		return '('
	if c == '}':
		return '{'
	if c == ']':
		return '['
n = int(input())
for _ in range(n):
	S = input().strip()
	good = True
	cstack = []
	for c in S:
		if c in ['{', '[', '(']:
			cstack.append(c)
		elif cstack and cstack.pop() == opposite(c):
			continue
		else:
			good = False
			break
	if good == True and len(cstack) == 0:
		print('YES')
	else:
		print('NO')


match = {'(': ')', '[': ']', '{': '}'}
for _ in range(int(input())):
	passes = True
	stack = list()
	for c in input():
		if c in '([{':
			stack.append(c)
		elif not (stack and match[stack.pop()] == c):
			passes = False
			break
	print('YES' if passes and (not stack) else 'NO')


import sys
T = int(input())
strings = []
for i in range(0, T):
	s = str(input().strip(' '))
	strings.append(s)

def check(s):
	if s.strip(' ') == '':
		return 'NO'
	curve = 0
	round_ = 0
	square = 0
	who_was_last = []
	for j in range(0, len(s)):
		if s[j] == '(':
			round_ += 1
			who_was_last.append('(')
		if s[j] == '[':
			square += 1
			who_was_last.append('[')
		if s[j] == '{':
			curve += 1
			who_was_last.append('{')
		if s[j] == ')':
			round_ -= 1
			if round_ < 0:
				return 'NO'
			if who_was_last[len(who_was_last) - 1] != '(':
				return 'NO'
			who_was_last = who_was_last[0:len(who_was_last) - 1]
		if s[j] == ']':
			square -= 1
			if square < 0:
				return 'NO'
			if who_was_last[len(who_was_last) - 1] != '[':
				return 'NO'
			who_was_last = who_was_last[0:len(who_was_last) - 1]
		if s[j] == '}':
			curve -= 1
			if curve < 0:
				return 'NO'
			if who_was_last[len(who_was_last) - 1] != '{':
				return 'NO'
			who_was_last = who_was_last[0:len(who_was_last) - 1]
	if curve > 0 or square > 0 or round_ > 0:
		return 'NO'
	return 'YES'
for i in range(0, T):
	print(check(strings[i]))


num = int(input())
lst_in = [input() for i in range(num)]
cl_op = {'}': '{', ')': '(', ']': '['}

def is_balanced(seq):
	stack = []
	for s in seq:
		if s in cl_op.values():
			stack.append(s)
		elif s in cl_op.keys() and len(stack) > 0 and (stack.pop() == cl_op[s]):
			continue
		else:
			return False
	return len(stack) == 0
for item in lst_in:
	if is_balanced(item):
		print('YES')
	else:
		print('NO')


def balanced_braces(s):
	braces = []
	for brace in s:
		if brace in '{[(':
			braces.append(brace)
		else:
			try:
				if brace == '}' and braces[-1] == '{':
					braces.pop()
				elif brace == ']' and braces[-1] == '[':
					braces.pop()
				elif brace == ')' and braces[-1] == '(':
					braces.pop()
				else:
					return False
			except IndexError:
				return False
	if len(braces) > 0:
		return False
	return True
N = int(input().strip())
for n in range(N):
	line = input().strip()
	if balanced_braces(line):
		print('YES')
	else:
		print('NO')


def main():
	t = input()
	items = []
	items.append(t[0])
	res = True
	for i in range(1, len(t)):
		if t[i] == '(' or t[i] == '{' or t[i] == '[':
			items.append(t[i])
		elif items.__len__() != 0:
			if t[i] == ')' and items[items.__len__() - 1] == '(':
				items.pop()
			elif t[i] == '}' and items[items.__len__() - 1] == '{':
				items.pop()
			elif t[i] == ']' and items[items.__len__() - 1] == '[':
				items.pop()
			else:
				items.append(t[i])
		elif len(t) != 0:
			res = False
	if items.__len__() == 0 and res == True:
		print('YES')
	else:
		print('NO')
N = int(input())
for _ in range(N):
	main()


n = int(input())
for i in range(n):
	string = input()
	balanced = True
	stack = []
	for c in string:
		if c == '{':
			stack.append('}')
		elif c == '(':
			stack.append(')')
		elif c == '[':
			stack.append(']')
		elif not stack or stack.pop() != c:
			balanced = False
			break
	if stack:
		balanced = False
	if balanced:
		print('YES')
	else:
		print('NO')


testcases = int(input().strip())
for test in range(testcases):
	s = input().strip()
	stack = []
	processed = 0
	for c in s:
		processed += 1
		if c in '{[(':
			stack.append(c)
		elif c in '}])' and stack:
			match = stack.pop()
			if match == '{' and c == '}' or (match == '(' and c == ')') or (match == '[' and c == ']'):
				pass
			else:
				stack.append(match)
				break
		else:
			break
	if processed != len(s) or stack:
		print('NO')
	else:
		print('YES')


from collections import deque

def find_parens(parens):
	paren_dic = {'[': ']', '{': '}', '(': ')'}
	seq = deque()
	for i in parens:
		if i in '[{(':
			seq.append(paren_dic[i])
		elif i in ']})':
			if len(seq) > 0:
				t = seq.pop()
				if not i == t:
					print('NO')
					return
			else:
				print('NO')
				return
	if len(seq) == 0:
		print('YES')
	else:
		print('NO')
T = int(input())
for i in range(T):
	find_parens(input())


def check_if_valid(brackets):
	valid_bracket_pairs = {'{': '}', '[': ']', '(': ')'}
	stack = []
	for element in brackets:
		if element in valid_bracket_pairs.keys():
			stack.append(valid_bracket_pairs[element])
		elif len(stack) > 0 and element == stack[-1]:
			stack.pop()
		else:
			return 'NO'
	if len(stack) == 0:
		return 'YES'
	else:
		return 'NO'
number_inputs = int(input())
for inp in range(number_inputs):
	print(check_if_valid(input()))


def is_pair(parentheses, opening, closing):
	return any((x[0] == opening and x[1] == closing for x in parentheses))
T = int(input().strip())
parentheses = [['{', '}'], ['[', ']'], ['(', ')']]
for i in range(T):
	parenthesis = input().strip()
	list = []
	balanced = True
	for character in parenthesis:
		if character in [x[0] for x in parentheses]:
			list.append(character)
		elif character in [x[1] for x in parentheses]:
			if not list or not is_pair(parentheses, list.pop(), character):
				balanced = False
				break
	if list:
		balanced = False
	print('YES' if balanced else 'NO')


match = {'(': ')', '[': ']', '{': '}'}
for _ in range(int(input())):
	passes = True
	stack = list()
	for c in input():
		if c in '([{':
			stack.append(c)
		elif not (stack and match[stack.pop()] == c):
			passes = False
			break
	print('YES' if passes and (not stack) else 'NO')


def main():
	n = int(input().strip())
	for _ in range(n):
		s = input().strip()
		stack = []
		balanced = True
		for ch in s:
			if ch in ['(', '{', '[']:
				stack.append(ch)
			elif len(stack) == 0:
				balanced = False
				break
			elif ch == ')' and stack.pop() != '(':
				balanced = False
				break
			elif ch == '}' and stack.pop() != '{':
				balanced = False
				break
			elif ch == ']' and stack.pop() != '[':
				balanced = False
				break
		print('YES' if balanced and len(stack) == 0 else 'NO')
main()


def balanced_parentheses(s):
	openings = '{[('
	endings = '}])'
	matches = {'}': '{', ']': '[', ')': '('}
	stack = []
	for (i, c) in enumerate(s):
		if c in openings:
			stack.append(c)
		elif c in endings and stack and (stack[-1] == matches[c]):
			stack.pop()
		else:
			return False
	return len(stack) == 0
n = int(input())
for _ in range(n):
	print('YES' if balanced_parentheses(input().rstrip()) else 'NO')


n = int(input())
dict = {'{': '}', '(': ')', '[': ']'}
for _ in range(n):
	s = input()
	stack = []
	p = True
	for i in s:
		if i in '({[':
			stack.append(i)
		elif not (stack and dict[stack.pop()] == i):
			p = False
			break
	print('YES' if not stack and p else 'NO')


n = int(input().strip())
d = {')': '(', '}': '{', ']': '['}
for i in range(n):
	A = [x for x in input().strip()]
	q = []
	for a in A:
		if a in d.values():
			q.append(a)
		elif len(q) == 0:
			print('NO')
			break
		elif q.pop() != d[a]:
			print('NO')
			break
	else:
		if len(q) == 0:
			print('YES')
		else:
			print('NO')


def check_closer(c, opener, stack_c, other_openers, last_seen):
	if last_seen in other_openers:
		return (False, False)
	elif len(stack_c) > 0:
		stack_c.pop()
		return (stack_c, c)
	else:
		return (False, False)

def runme():
	closers = [')', ']', '}']
	for i in range(int(input())):
		last_seen = False
		stackp = []
		stackc = []
		stackb = []
		for c in input():
			if not last_seen:
				if c in closers:
					break
				last_seen = c
			if c in closers:
				if c == ')':
					(stackp, last_seen) = check_closer(c, '(', stackp, ['[', '{'], last_seen)
				elif c == ']':
					(stackb, last_seen) = check_closer(c, '[', stackb, ['(', '{'], last_seen)
				else:
					(stackc, last_seen) = check_closer(c, '{', stackc, ['(', '['], last_seen)
			else:
				last_seen = c
				if c == '(':
					stackp.append(c)
				elif c == '[':
					stackb.append(c)
				elif c == '{':
					stackc.append(c)
			if not last_seen:
				break
		if not last_seen or len(stackc + stackp + stackb) > 0:
			print('NO')
		else:
			print('YES')
runme()


import sys
rd = int(sys.stdin.readline().rstrip())
s = []
parant = {'{': '}', '(': ')', '[': ']', '}': '{', ')': '(', ']': '['}
for x in range(0, rd):
	st = sys.stdin.readline().rstrip()
	s = []
	for ch in st:
		if len(s) > 0:
			if parant[s[-1]] != ch:
				s.append(ch)
			else:
				s.pop()
		else:
			s.append(ch)
	if len(s) == 0:
		print('YES')
	else:
		print('NO')


def parentheses(exp):
	stack = []
	for x in exp:
		if x == '[' or x == '{' or x == '(':
			stack.append(x)
		elif x == ']':
			if len(stack) != 0 and stack[-1] == '[':
				stack.pop()
			else:
				return 'NO'
		elif x == '}':
			if len(stack) != 0 and stack[-1] == '{':
				stack.pop()
			else:
				return 'NO'
		elif x == ')':
			if len(stack) != 0 and stack[-1] == '(':
				stack.pop()
			else:
				return 'NO'
	if len(stack) == 0:
		return 'YES'
	return 'NO'
[print(parentheses(input())) for x in range(int(input()))]


for _ in range(int(input())):
	(l, correct) = ([], True)
	for c in input():
		if c in '{([':
			l.append(c)
		elif c in '})]':
			if len(l) > 0 and (c == '}' and l[-1] == '{' or (c == ')' and l[-1] == '(') or (c == ']' and l[-1] == '[')):
				l.pop()
			else:
				correct = False
				break
	print('YES' if correct and len(l) == 0 else 'NO')


from collections import deque
T = int(input())
for t in range(T):
	expression = input()
	myStack = deque()
	expr_valid = True
	for ch in expression:
		if ch == '{' or ch == '(' or ch == '[':
			myStack.append(ch)
		elif myStack:
			topVal = myStack.pop()
			if ch == '}' and topVal != '{':
				expr_valid = False
				break
			elif ch == ')' and topVal != '(':
				expr_valid = False
				break
			elif ch == ']' and topVal != '[':
				expr_valid = False
				break
		else:
			expr_valid = False
			break
	if myStack:
		print('NO')
	elif expr_valid:
		print('YES')
	else:
		print('NO')


T = int(input().strip())
for t in range(T):
	l = input().strip()
	ps = []
	valid = 1
	for p in l:
		if p in ['{', '(', '[']:
			ps.append(p)
		elif not len(ps):
			valid = 0
			break
		else:
			lp = ps.pop()
			if not (lp == '{' and p == '}' or (lp == '(' and p == ')') or (lp == '[' and p == ']')):
				valid = 0
				break
	print('YES' if valid and (not len(ps)) else 'NO')


import math
left = ['[', '(', '{']
right = [']', ')', '}']
n = int(input())
for _ in range(n):
	stack = []
	inputs = input()
	string = [char for char in inputs]
	if not len(string) % 2 == 0:
		print('NO')
		continue
	toprint = 'YES'
	for char in string:
		if char in left:
			stack.append(char)
		elif char in right:
			if not len(stack) > 0:
				toprint = 'NO'
				break
			value = stack.pop()
			if not left.index(value) == right.index(char):
				toprint = 'NO'
		else:
			toprint = 'NO'
	if len(stack) > 0:
		toprint = 'NO'
	print(toprint)


from collections import deque
openers = ['[', '{', '(']
closers = [']', '}', ')']

def check_balance(string):
	stack = deque()
	for character in string:
		if character in openers:
			stack.append(character)
		else:
			if len(stack) < 1:
				return False
			if closers[openers.index(stack.pop())] != character:
				return False
	return len(stack) == 0
t = int(input().strip())
for test in range(t):
	string = input().strip()
	if check_balance(string):
		print('YES')
	else:
		print('NO')


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

def balanced(parens):
	if len(parens) % 2 != 0:
		return False
	stack = []
	for paren in parens:
		if paren in '{[(':
			stack.append(paren)
		else:
			if len(stack) == 0:
				return False
			if map[paren] != stack.pop():
				return False
	return len(stack) == 0
lines = int(input())
for i in range(lines):
	line = input()
	if balanced(line):
		print('YES')
	else:
		print('NO')


def parChecker(string):
	balanced = True
	index = 0
	stack = []
	while index < len(string) and balanced:
		if string[index] in '({[':
			stack.append(string[index])
		elif len(stack) == 0:
			balanced = False
		else:
			top = stack.pop()
			if not matches(top, string[index]):
				balanced = False
		index += 1
	if balanced and len(stack) == 0:
		print('YES')
	else:
		print('NO')

def matches(open, close):
	openers = '({['
	closers = ')}]'
	return openers.index(open) == closers.index(close)
n = int(input())
for i in range(n):
	string = input()
	parChecker(string)


open_brackets = '{,[,('

def get_reversed(bracket):
	if bracket == '{':
		return '}'
	elif bracket == '(':
		return ')'
	elif bracket == '[':
		return ']'

def bracket_tes(inp, brackets_stack):
	for each in inp:
		if each in open_brackets:
			brackets_stack.append(each)
		elif brackets_stack:
			popped_bracket = brackets_stack.pop()
			reversed_closing_bracket = get_reversed(popped_bracket)
			if reversed_closing_bracket != each:
				return False
		else:
			return False
	if len(brackets_stack) == 0:
		return True
	else:
		return False
N = int(input())
while N > 0:
	brackets_stack = []
	inp = input()
	if bracket_tes(inp, brackets_stack):
		print('YES')
	else:
		print('NO')
	N -= 1


import sys
N = int(sys.stdin.readline())
openBracket = ['{', '[', '(']
closeBracket = ['}', ']', ')']

def solution(line):
	stack = []
	for c in line:
		if c in openBracket:
			stack.append(c)
		if c in closeBracket:
			try:
				old = stack.pop(-1)
			except Exception:
				return 'NO'
			if openBracket.index(old) != closeBracket.index(c):
				return 'NO'
	if len(stack) == 0:
		return 'YES'
	return 'NO'
for i in range(N):
	line = sys.stdin.readline()
	print(solution(line))


def matcher(b):
	if b == '[':
		return ']'
	elif b == '{':
		return '}'
	elif b == '(':
		return ')'
	else:
		return None
t = int(input())
for i in range(t):
	usr = input()
	valid = 'YES'
	i = 0
	s = []
	if len(usr) % 2 != 0:
		valid = 'NO'
	while valid == 'YES' and i < len(usr):
		b = usr[i]
		if b == '[' or b == '(' or b == '{':
			s.append(b)
		elif s == []:
			valid = 'NO'
		elif matcher(s[-1]) == b:
			s.pop()
		else:
			valid = 'NO'
		i += 1
	if s == [] and valid == 'YES':
		print(valid)
	else:
		print('NO')


class Stack:

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

	def push(self, data):
		self._storage.append(data)

	def pop(self):
		return self._storage.pop()

	def is_empty(self):
		return len(self._storage) == 0

	def __str__(self):
		return self._storage.__str__()
n = int(input())
for i in range(n):
	stack = Stack()
	is_balanced = True
	s = str(input())
	for char in s:
		if char == '(' or char == '[' or char == '{':
			stack.push(char)
		elif stack.is_empty() and (char == ')' or char == '}' or char == ']'):
			is_balanced = False
		elif char == ')' and stack.pop() != '(' or (char == '}' and stack.pop() != '{') or (char == ']' and stack.pop() != '['):
			is_balanced = False
		if not is_balanced:
			break
	if not stack.is_empty():
		is_balanced = False
	if is_balanced:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	stack = []
	s = input()
	closed = True
	for c in s:
		if c in ['{', '[', '(']:
			stack.append(c)
		else:
			if len(stack) == 0:
				closed = False
				break
			if c == '}' and stack[-1] == '{':
				stack.pop()
			elif c == ']' and stack[-1] == '[':
				stack.pop()
			elif c == ')' and stack[-1] == '(':
				stack.pop()
			else:
				closed = False
				break
	if len(stack) == 0 and closed:
		print('YES')
	else:
		print('NO')


class Empty(Exception):
	pass

class ArrayStack(object):

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

	def __len__(self):
		return len(self._data)

	def push(self, item):
		self._data.append(item)

	def is_empty(self):
		return len(self._data) == 0

	def top(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data[-1]

	def pop(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data.pop()

def is_matched(expr):
	s = ArrayStack()
	left_syms = '[({'
	right_syms = '])}'
	for c in expr:
		if c in left_syms:
			s.push(c)
		elif c in right_syms:
			if s.is_empty():
				return False
			if left_syms.index(s.pop()) != right_syms.index(c):
				return False
	return s.is_empty()
try:
	n = int(input())
except ValueError:
	print('Not a number')
while n > 0:
	query = input()
	result = is_matched(query)
	if result is True:
		print('YES')
	else:
		print('NO')
	n -= 1


class Empty(Exception):
	pass

class ArrayStack(object):

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

	def __len__(self):
		return len(self._data)

	def push(self, item):
		self._data.append(item)

	def is_empty(self):
		return len(self._data) == 0

	def top(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data[-1]

	def pop(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data.pop()

def is_matched(expr):
	s = ArrayStack()
	left_syms = '[({'
	right_syms = '])}'
	for c in expr:
		if c in left_syms:
			s.push(c)
		elif c in right_syms:
			if s.is_empty():
				return False
			if left_syms.index(s.pop()) != right_syms.index(c):
				return False
	return s.is_empty()
try:
	n = int(input())
except ValueError:
	print('Not a number')
while n > 0:
	query = input()
	result = is_matched(query)
	if result is True:
		print('YES')
	else:
		print('NO')
	n -= 1


match = {'(': ')', '[': ']', '{': '}'}
for _ in range(int(input())):
	passes = True
	stack = list()
	for c in input():
		if c in '([{':
			stack.append(c)
		elif not (stack and match[stack.pop()] == c):
			passes = False
			break
	print('YES' if passes and (not stack) else 'NO')


import re
N = int(input().strip())

def is_valid(s):
	stack = []
	L = list(s)
	for paren in L:
		if paren in ['(', '[', '{']:
			stack.append(paren)
		elif paren in [')', ']', '}']:
			if not stack:
				return 'NO'
			if not re.match('(\\(\\)|\\[\\]|\\{\\})', ''.join((stack[-1], paren))):
				return 'NO'
			else:
				stack.pop()
	if stack:
		return 'NO'
	return 'YES'
for i in range(0, N):
	print(is_valid(input().strip()))


def balance_check(s):
	if len(s) % 2 != 0:
		return 'NO'
	opening = set('([{')
	matching = set([('(', ')'), ('[', ']'), ('{', '}')])
	stack = []
	for paren in s:
		if paren in opening:
			stack.append(paren)
		elif len(stack) == 0:
			return 'NO'
		else:
			last = stack.pop()
			if (last, paren) not in matching:
				return 'NO'
	if len(stack) != 0:
		return 'NO'
	else:
		return 'YES'
t = int(input())
for i in range(t):
	print(balance_check(input()))


def balance(expr):
	opens = '{[('
	closes = '}])'
	s = []
	balanced = 0
	for i in expr:
		if i in opens:
			s.append(i)
			balanced = 0
			continue
		else:
			if s == []:
				return 'NO'
			if opens.index(s[-1]) == closes.index(i):
				balanced = 1
				s.pop()
				continue
			else:
				return 'NO'
	if balanced:
		return 'YES'
	else:
		return 'NO'
n = int(input())
for i in range(n):
	expr = input()
	print(balance(expr.strip()))


match = {'}': '{', ']': '[', ')': '('}
T = int(input())
for _ in range(T):
	s = input()
	stack = []
	for ch in s:
		if ch in '{[(':
			stack.append(ch)
		elif not stack or match[ch] != stack.pop():
			print('NO')
			break
	else:
		print('NO' if stack else 'YES')


def IsBalanced(S):
	stack = []
	for c in S:
		if c == '(' or c == '[' or c == '{':
			stack.append(c)
		else:
			if len(stack) == 0:
				print('NO')
				return
			item = stack.pop()
			if item == '(' and c == ')' or (item == '{' and c == '}') or (item == '[' and c == ']'):
				continue
			else:
				print('NO')
				return
	if len(stack) == 0:
		print('YES')
	else:
		print('NO')
N = int(input())
for _ in range(0, N):
	inp = input()
	IsBalanced(inp)


T = int(input())
matches = {'{': '}', '(': ')', '[': ']'}

def balanced(string):
	s = []
	for char in string:
		if char in matches:
			s.append(char)
		elif len(s) == 0 or matches[s.pop(-1)] != char:
			return False
	return len(s) == 0
for _ in range(T):
	print('YES' if balanced(input().strip()) else 'NO')


n = int(input())
ls = []
msg = ''
for i in range(n):
	s = input()
	msg = ''
	ls = []
	for c in s:
		if c == '(' or c == '[' or c == '{':
			ls.append(c)
		else:
			if len(ls) == 0:
				msg = 'NO'
				break
			ch = ls.pop()
			if c == ')' and ch == '(' or (c == ']' and ch == '[') or (c == '}' and ch == '{'):
				continue
			else:
				msg = 'NO'
				break
	if msg != '':
		print(msg)
	elif len(ls) != 0:
		print('NO')
	else:
		print('YES')


def delimiters(brackets):
	if len(brackets) % 2 != 0:
		return False
	stack = []
	for b in brackets:
		if b == '(' or b == '[' or b == '<' or (b == '{'):
			stack.append(b)
		elif len(stack) == 0:
			return False
		elif b == ')' and stack[len(stack) - 1] == '(':
			stack = stack[:len(stack) - 1]
		elif b == ']' and stack[len(stack) - 1] == '[':
			stack = stack[:len(stack) - 1]
		elif b == '>' and stack[len(stack) - 1] == '<':
			stack = stack[:len(stack) - 1]
		elif b == '}' and stack[len(stack) - 1] == '{':
			stack = stack[:len(stack) - 1]
		else:
			return False
	if len(stack) == 0:
		return True
	return False
T = int(input().strip())
for i in range(0, T):
	if delimiters(input().strip()):
		print('YES')
	else:
		print('NO')


def closes(close_char, open_char):
	return close_char == ']' and open_char == '[' or (close_char == '}' and open_char == '{') or (close_char == ')' and open_char == '(')

def run_cmd(command):
	openChars = []
	for char in command:
		if char == '{' or char == '[' or char == '(':
			openChars.append(char)
		if char == '}' or char == ']' or char == ')':
			if len(openChars) == 0:
				print('NO')
				return
			removedVal = openChars.pop()
			if not closes(char, removedVal):
				print('NO')
				return
	if len(openChars) == 0:
		print('YES')
	else:
		print('NO')
commands = input()
for i in range(int(commands)):
	run_cmd(input())


def is_balanced(s):
	stack = []
	for c in s:
		if c in ('{', '[', '('):
			stack.append(c)
		else:
			if len(stack) == 0:
				return False
			o_c = stack.pop()
			if (o_c, c) not in (('[', ']'), ('{', '}'), ('(', ')')):
				return False
	return len(stack) == 0
n = int(input().strip())
for _ in range(n):
	print('YES' if is_balanced(input()) else 'NO')


T = int(input())
for i in range(T):
	stack = []
	expression = input()
	balanced = 'YES'
	for j in expression:
		if j == '[' or j == '{' or j == '(':
			stack.append(j)
		elif not stack:
			balanced = 'NO'
			break
		else:
			val = stack.pop()
			if j == ']' and val != '[' or (j == '}' and val != '{') or (j == ')' and val != '('):
				balanced = 'NO'
				break
	if len(stack) != 0:
		balanced = 'NO'
	print(balanced)


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

def parens_match(left_paren, right_paren):
	return open_paren_match[left_paren] == right_paren
tests_cnt = int(input().strip())
for _ in range(tests_cnt):
	s = list(input().strip())
	paren_stack = [s.pop()]
	output = 'YES'
	while s:
		paren = s[-1]
		if paren in open_paren_match:
			if not paren_stack:
				break
			elif parens_match(paren, paren_stack[-1]):
				paren_stack.pop()
				s.pop()
			else:
				break
		else:
			paren_stack.append(s.pop())
	print('YES' if len(paren_stack) == 0 and len(s) == 0 else 'NO')


import sys

def match(open_par, close_par):
	return open_par == '(' and close_par == ')' or (open_par == '[' and close_par == ']') or (open_par == '{' and close_par == '}')
num_lines = eval(input())
lines = []
for line in range(num_lines):
	lines.append(input())
for line in lines:
	open_pars = []
	matching = True
	for char in line:
		if char == '(' or char == '[' or char == '{':
			open_pars.append(char)
		elif len(open_pars) > 0:
			open_par = open_pars.pop()
			matching = matching and match(open_par, char)
		else:
			matching = False
	print('YES' if matching and len(open_pars) == 0 else 'NO')


ouvre = {'{', '[', '('}
correspondance = {'}': '{', ']': '[', ')': '('}
N = int(input())
for i in range(N):
	ok = True
	stack = list()
	for c in input():
		if c in ouvre:
			stack.append(c)
		elif len(stack) == 0 or correspondance[c] != stack.pop(-1):
			print('NO')
			ok = False
			break
	if ok and len(stack) != 0:
		print('NO')
		ok = False
	if ok:
		print('YES')


for _ in range(int(input())):
	s = input()
	l = []
	flag = True
	for i in s:
		if i == '(' or i == '{' or i == '[':
			l.append(i)
		elif i == ')':
			if len(l) == 0 or l.pop() != '(':
				flag = False
				break
		elif i == '}':
			if len(l) == 0 or l.pop() != '{':
				flag = False
				break
		elif len(l) == 0 or l.pop() != '[':
			flag = False
			break
	if flag and len(l) == 0:
		print('YES')
	else:
		print('NO')


import sys
STARTING_S = ['(', '[', '{']
ENDING_S = [')', ']', '}']

def check_balance(line):
	stack = []
	for c in line:
		if c in STARTING_S:
			stack.append(c)
		elif c in ENDING_S:
			if not stack:
				return 'NO'
			start = stack.pop()
			if ENDING_S.index(c) != STARTING_S.index(start):
				return 'NO'
	return 'YES' if not stack else 'NO'
n = int(sys.stdin.readline())
for i in range(n):
	print(check_balance(sys.stdin.readline()))


class Stack:

	def __init__(self, data=None):
		self.data = data
		if self.data is None:
			self.data = []

	def push(self, data):
		self.data.append(data)

	def pop(self):
		if len(self.data) > 0:
			return self.data.pop()
		else:
			return None

	def is_empty(self):
		if len(self.data) == 0:
			return True
		else:
			return False

def balanced_parens(paren_str):
	s = Stack()
	openers = {'}': '{', ')': '(', ']': '['}
	for i in paren_str:
		if i in openers.values():
			s.push(i)
		else:
			c = s.pop()
			if c != openers[i]:
				print('NO')
				return
	if s.is_empty():
		print('YES')
	else:
		print('NO')
n = int(input().strip())
for i in range(n):
	curstr = input().strip()
	balanced_parens(curstr)


d = {'}': '{', ']': '[', ')': '('}
for _ in range(int(input())):
	isBalanced = True
	stack = []
	for (i, c) in enumerate(input()):
		if c == '{' or c == '[' or c == '(':
			stack.append(c)
		elif not stack or d[c] != stack.pop():
			isBalanced = False
			break
	print('YES' if isBalanced and (not stack) else 'NO')


N = int(input())
opposites = {'}': '{', ']': '[', ')': '('}
for i in range(N):
	s = input().strip()
	stack = []
	for ch in s:
		if len(stack) > 0 and stack[-1] == opposites.get(ch):
			stack.pop()
		else:
			stack.append(ch)
	if len(stack) > 0:
		print('NO')
	else:
		print('YES')


n = int(input().strip())
bracketStrings = []
for i in range(n):
	bracketStrings.insert(i, input())
openingBrackets = ['(', '[', '{']
closingBrackets = [')', ']', '}']
for bracketString in bracketStrings:
	errors = False
	stack = []
	for bracket in bracketString:
		if bracket in openingBrackets:
			stack.append(bracket)
		else:
			bracketIndex = closingBrackets.index(bracket)
			if len(stack) == 0 or stack.pop() != openingBrackets[bracketIndex]:
				errors = True
				break
	print('YES' if not errors and len(stack) == 0 else 'NO')


def balanced(p):
	opening = set('({[')
	match = set([('(', ')'), ('[', ']'), ('{', '}')])
	stack = []
	for c in p:
		if c in opening:
			stack.append(c)
		else:
			if len(stack) == 0:
				return False
			last = stack.pop()
			if (last, c) not in match:
				return False
	return len(stack) == 0

def test(tests):
	for t in tests:
		if balanced(t[0]):
			print('YES')
		else:
			print('NO')
N = int(input())
s = []
for i in range(0, N):
	s.append(input().strip().split(' '))
test(s)


def isMatch(a, b):
	if a == '{' and b == '}' or (a == '[' and b == ']') or (a == '(' and b == ')'):
		return True
	else:
		return False
linesToRead = int(input())
linesRead = 0
for i in range(linesToRead):
	line = input()
	stack = []
	result = ''
	for token in line:
		if token in '{([':
			stack.append(token)
		else:
			if len(stack) > 0:
				lastOpen = stack.pop()
			else:
				lastOpen = '*'
			if not isMatch(lastOpen, token):
				result = 'NO'
				break
	if len(stack) == 0 and result == '':
		result = 'YES'
	else:
		result = 'NO'
	print(result)


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

def isBalanced(S):
	stack = []
	for c in S:
		if c in '{[(':
			stack.append(c)
		elif not stack or match[c] != stack.pop():
			return False
	return not stack
for _ in range(int(input())):
	if isBalanced(input()):
		print('YES')
	else:
		print('NO')


def check_brackets(inp):
	l = []
	flag = 1
	for i in inp:
		if i == '(' or i == '{' or i == '[':
			l.append(i)
		elif i == ')':
			if len(l) > 0 and l.pop() == '(':
				pass
			else:
				flag = 0
				break
		elif i == '}':
			if len(l) > 0 and l.pop() == '{':
				pass
			else:
				flag = 0
				break
		elif i == ']':
			if len(l) > 0 and l.pop() == '[':
				pass
			else:
				flag = 0
				break
	if flag == 0:
		return 'NO'
	elif len(l) == 0 and flag == 1:
		return 'YES'
	else:
		return 'NO'
n = eval(input())
for i in range(n):
	inp = input()
	res = check_brackets(inp)
	print(res)


T = int(input())
while T > 0:
	s = input()
	stack = []
	for ch in s:
		if ch in '{[(':
			stack.append(ch)
		elif len(stack) == 0:
			print('NO')
			break
		elif ch == ')' and stack.pop() != '(':
			print('NO')
			break
		elif ch == '}' and stack.pop() != '{':
			print('NO')
			break
		elif ch == ']' and stack.pop() != '[':
			print('NO')
			break
	else:
		if len(stack) == 0:
			print('YES')
		else:
			print('NO')
	T -= 1


def check(stack):
	accept = ['{}', '[]', '()']
	for c in stack:
		if c not in accept:
			return 'NO'
	return 'YES'

def meow(s):
	opens = ['{', '[', '(']
	closes = ['}', ']', ')']
	stack = []
	retVal = []
	length = len(s)
	if length % 2 != 0 or s[0] in closes:
		return 'NO'
	for char in s:
		if char in opens:
			stack.append(char)
		elif stack:
			paren = stack.pop()
			meow = paren + char
			retVal.append(meow)
	if stack:
		return 'NO'
	else:
		return check(retVal)
leng = int(input())
for i in range(leng):
	s = input()
	print(meow(s))


def match(a, b):
	return a == '(' and b == ')' or (a == '[' and b == ']') or (a == '{' and b == '}')

def is_valid(string):
	stack = []
	try:
		for c in string:
			if c in ('(', '[', '{'):
				stack.append(c)
			elif not match(stack.pop(), c):
				return False
		return len(stack) == 0
	except:
		return False
N = int(input())
for _ in range(N):
	if is_valid(input()):
		print('YES')
	else:
		print('NO')


opening = ['{', '[', '(']
closing = ['}', ']', ')']

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

def isBalanced(seq):
	seen = []
	for item in seq:
		if item in opening:
			seen.append(item)
		elif len(seen) != 0:
			check = seen.pop()
			if not isMatch(check, item):
				return False
		else:
			return False
	return len(seen) == 0
i = 0
cases = int(input())
while i < cases:
	i += 1
	case = input()
	if isBalanced(case):
		print('YES')
	else:
		print('NO')


test_cases = int(input())
for _ in range(test_cases):
	line = input()
	stack = []
	cs = []
	opened = []
	invalid = False
	for c in line:
		if c == '{':
			opened.append(c)
			stack.append(c)
		elif c == '(':
			opened.append(c)
			stack.append(c)
		elif c == '[':
			opened.append(c)
			stack.append(c)
		elif c == ')':
			if len(opened) == 0 or opened[len(opened) - 1] != '(':
				invalid = True
			else:
				opened.pop()
				stack.pop()
		elif c == ']':
			if len(opened) == 0 or opened[len(opened) - 1] != '[':
				invalid = True
			else:
				opened.pop()
				stack.pop()
		elif c == '}':
			if len(opened) == 0 or opened[len(opened) - 1] != '{':
				invalid = True
			else:
				opened.pop()
				stack.pop()
	if invalid == True:
		print('NO')
	elif len(stack) == 0:
		print('YES')
	else:
		print('NO')


from collections import deque
n = int(input().strip())

def last_element(d):
	try:
		e = d.pop()
		d.append(e)
		return e
	except IndexError:
		return None
for i in range(n):
	balanced = True
	s = input().strip()
	stack = deque()
	for c in s:
		if c in '[{(':
			stack.append(c)
		else:
			e = last_element(stack)
			if e is None:
				balanced = False
				break
			elif e == '(' and c == ')':
				stack.pop()
			elif e == '[' and c == ']':
				stack.pop()
			elif e == '{' and c == '}':
				stack.pop()
			else:
				balanced = False
				break
	if len(stack) > 0:
		balanced = False
	if balanced:
		print('YES')
	else:
		print('NO')


T = int(input())
while T > 0:
	T -= 1
	s = input()
	lefts = ['{', '(', '[']
	rights = ['}', ')', ']']
	goodpairs = list(zip(lefts, rights))
	stack = []
	passcase = True
	for c in s:
		if c in lefts:
			stack.append(c)
		elif not stack:
			passcase = False
			break
		else:
			left = stack.pop()
			right = c
			if (left, right) not in goodpairs:
				passcase = False
				break
	if stack:
		passcase = False
	if passcase:
		print('YES')
	else:
		print('NO')


from collections import deque
t = int(input())
stack = deque()
dicc = {')': '(', '}': '{', ']': '['}
for i in range(t):
	exp = input()
	stack.clear()
	for s in exp:
		if s in '({[':
			stack.append(s)
		elif len(stack) > 0:
			l = stack.pop()
			if dicc[s] is not l:
				stack.append(l)
				break
		else:
			stack.append('')
	print('YES' if len(stack) == 0 else 'NO', end='\n')


def isBalanced(b):
	stack = []
	balanced = True
	for i in b:
		if i == '(' or i == '{' or i == '[':
			stack.append(i)
		elif len(stack) > 0:
			if i == ')' and stack[-1] == '(' or (i == '}' and stack[-1] == '{') or (i == ']' and stack[-1] == '['):
				stack.pop()
		else:
			balanced = False
			break
	if len(stack) != 0:
		balanced = False
	return balanced
t = int(input())
while t:
	b = input()
	if isBalanced(b):
		print('YES')
	else:
		print('NO')
	t -= 1


def check_case(string):
	lngth = len(string)
	opn = ['[', '{', '(']
	clos = [']', '}', ')']
	if lngth % 2 != 0 or string[0] in clos:
		return 'NO'
	balanced_pairs = list((''.join(x) for x in zip(opn, clos)))
	pairs = []
	stack = []
	for parenth in string:
		if parenth in opn:
			stack.append(parenth)
		elif stack:
			opened = stack.pop()
			closing = parenth
			joined = ''.join([opened, closing])
			pairs.append(joined)
	if stack:
		return 'NO'

	def balanced(pairs):
		for p in pairs:
			if p not in balanced_pairs:
				return 'NO'
		return 'YES'
	return balanced(pairs)
tests = int(input())
for i in range(tests):
	string = input()
	print(check_case(string))


num_input = input()
for x in range(int(num_input)):
	paren = input()
	stack = []
	balance = 'YES'
	for c in paren:
		if c == ')' or c == ']' or c == '}':
			if not stack:
				balance = 'NO'
			else:
				opposite = stack.pop()
				if c == ')' and opposite != '(':
					balance = 'NO'
				if c == ']' and opposite != '[':
					balance = 'NO'
				if c == '}' and opposite != '{':
					balance = 'NO'
		else:
			stack.append(c)
	if len(stack) > 0:
		balance = 'NO'
	print(balance)


class Stack:

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

	def is_empty(self):
		return self.items == []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def peek(self):
		return self.items[-1]

	def size(self):
		return len(self.items)

def paren_checker(parens_string):
	s = Stack()
	balanced = True
	for paren in parens_string:
		if paren in '{[(':
			s.push(paren)
		elif s.is_empty():
			balanced = False
			break
		else:
			top = s.pop()
			if not matches(top, paren):
				balanced = False
				break
	if s.is_empty() and balanced:
		return 'YES'
	else:
		return 'NO'

def matches(opening, closing):
	return '{[('.index(opening) == '}])'.index(closing)
n = int(input().strip())
inputs = [input().strip() for i in range(n)]
for paren_string in inputs:
	print(paren_checker(paren_string))


def last(lst):
	if len(lst) > 0:
		return lst[len(lst) - 1]
	else:
		return None

def check(string):
	parens = []
	for char in string:
		if char == '{':
			parens.append('{')
		elif char == '[':
			parens.append('[')
		elif char == '(':
			parens.append('(')
		elif char == '}':
			if last(parens) == '{':
				parens.pop()
			else:
				return False
		elif char == ']':
			if last(parens) == '[':
				parens.pop()
			else:
				return False
		elif char == ')':
			if last(parens) == '(':
				parens.pop()
			else:
				return False
	return len(parens) == 0
N = int(input())
for unnecessary_iterator in range(N):
	if check(input()):
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	test = input()
	res = [0]
	for j in range(len(test)):
		if len(res) != 0 and (test[j] == ')') & (res[len(res) - 1] == '(') or (test[j] == '}') & (res[len(res) - 1] == '{') or (test[j] == ']') & (res[len(res) - 1] == '['):
			res.pop()
		else:
			res.append(test[j])
	if len(res) == 1:
		print('YES')
	else:
		print('NO')


class Stack:

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

	def push(self, what):
		self.items.append(what)

	def pop(self, what):
		if not self.items:
			return False
		if what == ')' and self.items[-1] == '(' or (what == ']' and self.items[-1] == '[') or (what == '}' and self.items[-1] == '{'):
			self.items.pop()
			return True
		return False

def nxt():
	s = input()
	stack = Stack()
	for elem in s:
		if elem == '(' or elem == '[' or elem == '{':
			stack.push(elem)
		elif not stack.pop(elem):
			print('NO')
			return
	if not stack.items:
		print('YES')
	else:
		print('NO')

def main():
	T = int(input())
	for test in range(T):
		nxt()
main()


N = int(input())
for i in range(N):
	my_stack = []
	my_list = list(input().strip())
	for j in range(len(my_list)):
		if len(my_stack) == 0:
			my_stack.append(my_list[j])
		elif my_stack[-1] == '{' and my_list[j] == '}' or (my_stack[-1] == '[' and my_list[j] == ']') or (my_stack[-1] == '(' and my_list[j] == ')'):
			my_stack.pop()
		else:
			my_stack.append(my_list[j])
	if len(my_stack) == 0:
		print('YES')
	else:
		print('NO')


n = int(input())
pairs = {'(': ')', '{': '}', '[': ']'}
for i in range(n):
	string = input()
	stack = []
	for i in string:
		if i in '{[(':
			stack.append(i)
		else:
			try:
				opposing = stack.pop()
				if i != pairs[opposing]:
					print('NO')
					break
			except:
				print('NO')
				break
	else:
		if len(stack) != 0:
			print('NO')
		else:
			print('YES')


n = int(input().strip())
strings = []
for i in range(n):
	strings.append(input().strip())

def pair(in_string):
	if in_string == '{':
		return '}'
	if in_string == '(':
		return ')'
	if in_string == '[':
		return ']'
for string in strings:
	trouble = False
	t1_stack = []
	for char in string:
		if char in ['{', '[', '(']:
			t1_stack.append(char)
		if char in ['}', ']', ')']:
			if len(t1_stack) == 0:
				print('NO')
				trouble = True
				break
			if char != pair(t1_stack.pop()):
				print('NO')
				trouble = True
				break
	if len(t1_stack) == 0 and (not trouble):
		print('YES')
	elif len(t1_stack) != 0 and (not trouble):
		print('NO')


i = int(input())
stack = []
oo = {'{': '}', '(': ')', '[': ']'}
oc = {'}': '{', ')': '(', ']': '['}
for x in range(i):
	r = input()
	isOk = True
	for c in r:
		if c in oo:
			stack.append(c)
			isOk = False
		else:
			if len(stack) == 0:
				isOk = False
				break
			nc = stack.pop(len(stack) - 1)
			if c != oo[nc]:
				isOk = False
				break
			else:
				isOk = True
	print('YES' if isOk else 'NO')


def isOpenClose(c1, c2):
	if c1 == '(' and c2 == ')':
		return True
	if c1 == '[' and c2 == ']':
		return True
	if c1 == '{' and c2 == '}':
		return True
	return False

def isOpen(c):
	if c == '(' or c == '[' or c == '{':
		return True
	return False
n = int(input())
for i in range(0, n):
	exp = input().strip()
	stack = []
	valid = True
	for c in exp:
		if isOpen(c):
			stack.append(c)
		elif len(stack) == 0 or not isOpenClose(stack.pop(), c):
			valid = False
			break
	if valid and len(stack) == 0:
		print('YES')
	else:
		print('NO')