赏月斋源码共享计划 第七期 括号匹配

技术文章 5个月前 完美者
1,418 0

标签:log   port   utf-8   from   是否有效   balance   find   共享   and   

题目:

字符串中有括号”()[]{}”,设计算法,判断该字符串是否有效
括号必须以正确的顺序配对,如:“()”、“()[]”是有效的,但“([)]”无效

 

解法一:

# coding=utf-8
from pythonds.basic.stack import Stack # 栈可以不用此包,入栈append,出栈pop

def parChecker(symbolString):
    s = Stack()
    balanced = True
    symbolList = list(symbolString)
    index = 0
    while balanced == True and index < len(symbolString):
        if symbolString[index] == "(":
            s.push(symbolString[index])
        else:       # symbolString=")"
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index += 1

    if s.isEmpty():
        balanced = True
    else:
        balanced = False

    # for i in symbolList:
    #     if i == ‘(‘:
    #         s.push(i)
    #     else:     # i == ‘)‘
    #         if s.isEmpty():
    #             balanced = False
    #         else:
    #             s.pop()   
    # if s.isEmpty():
    #     balanced = True
    # else:
    #     balanced = False

    return balanced

if __name__ == "__main__":
    symbolString = ‘(())()()()((()()(()())))(‘
    print(parChecker(symbolString))

  

解法二(更好):(来自https://blog.csdn.net/weixin_42018258/article/details/80579081)

def match_parentheses(s):
    # 把一个list当做栈使用
    ls = []
    parentheses = "()[]{}"
    for i in range(len(s)):
        si = s[i]
        # 如果不是括号则继续
        if parentheses.find(si) == -1:
            continue
        # 左括号入栈
        if si == ‘(‘ or si == ‘[‘ or si == ‘{‘:
            ls.append(si)
            continue
        if len(ls) == 0:
            return False
        # 出栈比较是否匹配
        p = ls.pop()
        if (p == ‘(‘ and si == ‘)‘) or (p == ‘[‘ and si == ‘]‘) or (p == ‘{‘ and si == ‘}‘):
            continue
        else:
            return False

    if len(ls) > 0:
        return False
    return True


if __name__ == ‘__main__‘:
    s = "{abc}{de}(f)[(g)"
    result = match_parentheses(s)
    print(s, result)
    s = "0{abc}{de}(f)[(g)]9"
    result = match_parentheses(s)
    print(s, result)

  

 

赏月斋源码共享计划 第七期 括号匹配

标签:log   port   utf-8   from   是否有效   balance   find   共享   and   

原文地址:https://www.cnblogs.com/sddai/p/13931209.html

版权声明:完美者 发表于 2020-11-06 2:07:04。
转载请注明:赏月斋源码共享计划 第七期 括号匹配 | 完美导航

暂无评论

暂无评论...