算法基础_栈_习题

关于栈的习题:

1 关于栈的习题([LeetCode] Valid Parentheses):

【原题】Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not
【意译】给一个只包含'(', ')', '{', '}', '[' 和 ']'的字符串,判断这个字符串是否合法(括号是否匹配)

这里用栈的思想解决,如果为{ [ {则压入栈中,否则检查栈顶元素,如果为对应的符号,则将栈顶出栈,否则则此字符串不合法。

def matchString(leftString, rightString):
    if (leftString == '(' and rightString == ')') or 
        (leftString == '{' and rightString == '}') or
        (leftString == '[' and rightString == ']'):
        return True
    return False

def checkIsLegal(checkString):
    list = []
    for s in checkString:
        if s == '(' or s == '{' or s == '[':
            list.append(s)
        else:
            if len(list) == 0:
                return False
            else:
                if matchString(list[(len(list))-1], s):
                    list.pop()
                else:
                    return False

    if len(list) == 0:
        return True
    else:
        return False

if __name__ == '__main__':

    print(checkIsLegal('((())){}{}'))

2(本题可选)关于栈的习题(LeetCodeLongest Valid Parentheses)

【原题】Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4
【意译】给定一个只包含字符'(' 和 ')'的字符串,找出最长的合法括号字串

# 先给这个队列加一个 (,
# 后面的按照 ( )进出栈,
# 如果这第一个添加的(也要出栈的话,那字符串到此就不合法了
# 输入每次到不合法的字符串的位置,将前面的放入数组,
# 结束之后会剩下一个字符串,检查这个字符串有多少个) 如果有n个), 那么截取第length-n*2位截取到第最后,将结果加入到数组中
# 获取数组中长度最大的字符串,即为正确结果

def longestLegalString(longString):
    #先给队列加一个 (
    list = ['(']
    legalStringList = []
    legalString = ''
    for s in longString:
        if s == '(':
            list.append(s)
            legalString = legalString + s
        else:
            if len(list) == 1:
                # 出现非法字符
                if len(legalString) > 0:
                    legalStringList.append(legalString)
                legalString = ''
            else:
                list.pop()
                legalString = legalString + s

    # 检查字符串有多少个) 如果有n个), 那么截取第length-n*2位截取到第最后
    if len(legalString) > 0:
        legalStringList.append(legalString[-legalString.count(')')*2:])

    if len(legalStringList) > 0:
        # 查找最大的
        longStringText = ''
        for i in range(len(legalStringList)):
            if len(legalStringList[i]) > len(longStringText):
                longStringText = legalStringList[i]

        print('longStringText = ' + longStringText)
    else:
        print('没有合法字符串')

if __name__ == '__main__':
    longestLegalString('())(((((((())()())))))))()())))()()(())))))))))')
    longestLegalString('))))')