Write a function called that takes a string of parentheses, and determines if the order of the parentheses is valid. The function should return `true` if the string is valid, and `false` if it's invalid.

## Examples

```
"()"              =>  true
")(()))"          =>  false
"("               =>  false
"(())((()())())"  =>  true
```

## Constraints

`0 <= input.length <= 100`

~~~if-not:javascript,go
Along with opening (`(`) and closing (`)`) parenthesis, input may contain any valid ASCII characters.  Furthermore, the input string may be empty and/or not contain any parentheses at all.  Do **not** treat other forms of brackets as parentheses (e.g. `[]`, `{}`, `<>`).
~~~

Difficulty: EASY

Starter code:
def valid_parentheses(string):
	

Solutions:
def valid_parentheses(string):
	cnt = 0
	for char in string:
		if char == '(':
			cnt += 1
		if char == ')':
			cnt -= 1
		if cnt < 0:
			return False
	return True if cnt == 0 else False


def valid_parentheses(string):
	count = 0
	for i in string:
		if i == '(':
			count += 1
		elif i == ')':
			count -= 1
		if count < 0:
			return False
	return count == 0


iparens = iter('(){}[]<>')
parens = dict(zip(iparens, iparens))
closing = parens.values()

def valid_parentheses(astr):
	stack = []
	for c in astr:
		d = parens.get(c, None)
		if d:
			stack.append(d)
		elif c in closing:
			if not stack or c != stack.pop():
				return False
	return not stack


class Stack:

	def __init__(self):
		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 is_empty(self):
		return self.items == []

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

def valid_parentheses(symbol_string):
	stack = Stack()
	for char in symbol_string:
		if char == '(':
			stack.push('(')
		elif char == ')':
			if stack.is_empty():
				return False
			else:
				stack.pop()
	if not stack.is_empty():
		return False
	else:
		return True


def valid_parentheses(string):
	string = ''.join((ch for ch in string if ch in '()'))
	while '()' in string:
		string = string.replace('()', '')
	return not string


import re
_regex = '[^\\(|\\)]'

def valid_parentheses(string):
	string = re.sub(_regex, '', string)
	while len(string.split('()')) > 1:
		string = ''.join(string.split('()'))
	return string == ''


def valid_parentheses(s):
	stack = 0
	for char in s:
		if char == '(':
			stack += 1
		if char == ')':
			if not stack:
				return False
			else:
				stack -= 1
	return not stack


import re

def valid_parentheses(s):
	try:
		re.compile(s)
	except:
		return False
	return True


def valid_parentheses(s):
	b = 0
	for c in s:
		if c == '(':
			b += 1
		if c == ')':
			b -= 1
			if b < 0:
				return False
	return b == 0


def valid_parentheses(string):
	stack = []
	for i in string:
		if i == '(':
			stack.append(i)
		elif i == ')' and (not stack):
			return False
		elif i == ')':
			stack.pop()
	return not stack


def valid_parentheses(string):
	open_counter = 0
	for i in string:
		if i == '(':
			open_counter = open_counter + 1
		if i == ')':
			open_counter = open_counter - 1
		if open_counter < 0:
			return False
	if open_counter == 0:
		return True
	return False


def valid_parentheses(string):
	new = ''.join([i for i in string if i in '()'])
	while '()' in new:
		new = new.replace('()', '')
	return len(new) == 0


def valid_parentheses(string):
	string = ''.join([x for x in string if x == '(' or x == ')'])
	before_reduce = len(string)
	string = string.replace('()', '')
	if string == '':
		return True
	elif before_reduce != len(string):
		return valid_parentheses(string)
	else:
		return False


def valid_parentheses(string):
	string = ''.join((x for x in string if x in ('(', ')')))
	while '()' in string:
		string = string.replace('()', '')
	return False if len(string) != 0 else True


def valid_parentheses(string):
	string = ''.join((i for i in string if i == '(' or i == ')'))
	while '()' in string:
		string = string.replace('()', '')
	return string == ''


def valid_parentheses(string):
	string = [c for c in string if not c.isalpha()]
	string = ''.join(string)
	while '()' in string:
		string = string.replace('()', '')
	return True if len(string) == 0 else False


def valid_parentheses(s):
	p = '()'
	s = ''.join([e for e in s if e in '()'])
	while p in s:
		s = s.replace(p, '')
	return not s


def valid_parentheses(string):
	open = 0
	for c in string:
		if c == '(':
			open += 1
		elif c == ')':
			open -= 1
		if open < 0:
			return False
	return open == 0


def valid_parentheses(string):
	i = 0
	for c in string:
		if c == '(':
			i += 1
		if c == ')':
			i -= 1
		if i < 0:
			return False
	return i == 0


def valid_parentheses(string):
	count = 0
	for c in [c for c in string if c in '()']:
		count += 1 if c == '(' else -1
		if count < 0:
			return False
	return count == 0


def valid_parentheses(string):
	string = ''.join([x for x in string if x in '()'])
	try:
		string = string.replace('()', '')
		return valid_parentheses(string) if string else True
	except:
		return False


def valid_parentheses(s):
	lvl = 0
	for c in s:
		lvl += (c == '(') - (c == ')')
		if lvl < 0:
			return False
	return not lvl


def valid_parentheses(string):
	depth = 0
	for i in string:
		if i == '(':
			depth += 1
		elif i == ')':
			depth -= 1
		if depth < 0:
			return False
	if depth == 0:
		return True
	else:
		return False


def valid_parentheses(string):
	count_open = 0
	count_close = 0
	index_open = 0
	index_closed = 0
	for s in string:
		if s == '(':
			count_open += 1
		elif s == ')':
			count_close += 1
			if count_close > count_open:
				return False
	if count_open != count_close:
		return False
	else:
		return True


import re

def valid_parentheses(string):
	s = ''.join([i for i in string if i in '()'])
	total = [string]
	while True:
		s = s.replace('()', '')
		total.append(s)
		if total[-1] == total[-2]:
			break
	return True if total[-1] == '' else False


def valid_parentheses(string):
	times = 0
	count = 0
	for i in string:
		if string[times] == '(':
			count += 1
		elif string[times] == ')':
			count -= 1
		print(count, i, times)
		times += 1
		if count < 0:
			return False
	if count == 0:
		return True
	else:
		return False


def valid_parentheses(string):
	str = string
	if str == '':
		return True
	if len(str) > 100:
		str = str[0:100]
	c_open = 0
	exc = 0
	for c in str:
		if c == '(':
			c_open += 1
		if c == ')':
			c_open -= 1
			if c_open < 0:
				exc = 1
				break
	if exc == 1 or c_open != 0:
		return False
	return True


def valid_parentheses(string):
	counter = 0
	for i in string:
		if i == '(':
			counter += 1
		if i == ')':
			counter -= 1
		if counter < 0:
			return False
	return counter == 0