题目

（5kyu）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.
示例：

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

限制：0 <= input.length <= 100
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. [], {}, <>).
题目大意是：给定一个字符串，判断其中所有的左括号和右括号是否正确匹配，一对左右括号中右括号不能在左括号左边，而且成对的左右括号中间不能有未匹配的左括号或右括号；要求输出布尔值True或False。

我的答案

我的思路是现将输入的字符串中所有'('和')'提取出来，保持顺序不变；然后遍历整个新字符串，如果出现一对相邻的'()'则消除；最后如果字符串为空，则为True；如果有落单的'('或')'，则为False。

op = {')': '('}
def valid_parentheses(string):
    s = ''
    for each in string:
        if each == '(' or each == ')':
            s += each
    temp = []
    for each in s:
        try:
            if temp and temp[-1] == op[each]:
                temp.pop()
            else:
                temp.append(each)
        except:
            temp.append(each)
    if temp:
        return False
    else:
        return True

当然解决方案还有优化的空间。

其他精彩答案

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

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

import re
_regex = "[^\(|\)]"
def valid_parentheses(string):
    string = re.sub(_regex, '', string)
    while len(string.split('()')) > 1:
        string = ''.join(string.split('()'))
    return string == ''