合法括号序列判断

[编程题]合法括号序列判断

热度指数：14765 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个字符串A和其长度n，请返回一个bool值代表它是否为一个合法的括号串（只能由括号组成）。

测试样例：

"(()())",6

返回：true

测试样例：

"()a()()",7

返回：false

测试样例：

"()(()()",7

返回：false

算法知识视频讲解

Python

华科平凡

python solution

使用一个栈来做，每当遇到左括号就放到栈里面，每当遇到右括号，先判断栈里面有没有左括号，如果有，弹出一个，如果没有，直接返回false。最终判断这个栈是否为空，如果为空，返回true，否则返回false。

class Parenthesis:
    def chkParenthesis(self, A, n):
        # write code here
        stack=[]
        for i in A:
            if i=="(":
                stack.append("(")
            elif i==")":
                if not stack:return False
                stack.pop()
        return stack==[]

发表于 2017-10-31 16:31:09 回复(0)

Python

Yannyezixin

递归版本：弹出合法的括号对

# -*- coding:utf-8 -*-

class Parenthesis:
    def chkParenthesis(self, A, n):
        if n <= 0:
            return False

        a = list(A)
        left = a.count('(')
        right = a.count(')')
        if left != right or left + right != n:
            return False
        b = []
        
        def check(b):
            if not b:
                return True
            tmp = b[:]
            idx = 0
            flag = False
            for i, j in zip(tmp, tmp[1:]):
                if i == '(' and j == ')':
                    flag = True
                    b[idx] = ''
                    b[idx + 1] = ''
                idx += 1
            if flag == False:
                return False
            else:
                b = [i for i in b if i != '']
                return check(b)
        
        return check(b)

非递归版本：使用栈,相当简单清晰

# -*- coding:utf-8 -*-

class Parenthesis:
    def chkParenthesis(self, A, n):
        a = list(A)
        
        stack = []
        for i in a:
            if i == '(':
                stack.append(i)
            elif i == ')':
                if not stack:
                    return False
                else:
                    stack.pop()
            else:
                return False
        
        return True

发表于 2016-08-05 11:41:03 回复(1)