您现在的位置是：首页 > Python

当前栏目

python实现括号匹配

Python 输出

2023-03-02 11:48:04 时间

**1.用一个栈【python中可以用List】就可以解决，时间和空间复杂度都是O(n)**

# 符号表
    SYMBOLS = { '}': '{', ']': '[', ')': '(', '>': '<'}
    SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.keys()
    
    def check(s):
        arr = []
        for c in s:
            if c in SYMBOLS_L:
                # 左符号入栈
                arr.append(c)
            elif c in SYMBOLS_R:
                # 右符号要么出栈，要么匹配失败
                if arr and arr[-1] == SYMBOLS[c]:
                    arr.pop()
                else:
                    return False
    
        return True
    
    print(check("3 * {3 +[(2 -3) * (4+5)]}"))
    print(check("3 * {3+ [4 - 6}]"))

**2.**

''' 遇到问题没人解答？小编创建了一个Python学习交流QQ群：531509025 寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！ '''
    # 存储左括号和右括号
    open_brackets = '([{<'
    close_brackets = ')]}>'
    # 映射左右括号便于出栈判断
    brackets_map = { ')': '(', ']': '[', '}': '{', '>': '<'}
    
    # 对于每一行数据，进行如下判定若括号为左括号，加入栈，若括号为右括号，判断是否跟栈尾括号对应，
    #若对应，弹出栈尾元素，若所有括号均正确闭合，则最后栈为空。
    for row in rows:
        stack = []
        label = True
        for char in row:
            if char in open_brackets:
                stack.append(char)
            elif char in close_brackets:
                if len(stack) < 1:
                    label = False
                    break
                elif brackets_map[char] == stack[-1]:
                    stack.pop()
                else:
                    label = False
                    break
            else:
                continue
        if stack != []:
            label = False
        print(label)
    
    rows = [
    '([<^>x[ ]{a}]{/}{t}g<^>)<{x}b>{x}<z({%}w >[b][c[c]]{<h>{h}}',
     '[/]{((x)({ {*}*}w)w){f}{v}[%(^[z]{u}{ })([[ ]-]h)]{c}(*)[y]}',
     '<<(^)z>>[b]< >[[(c)u[v]{z<b< >><b>}]g][/b[(])v(v)(+)](v)',
     '[[b]][(v)g]<z>([{ {<->+}e}[*]d<+>]g[[a] <+>(v){b}<e>]){a}[u]']

**3.在长度很大的时候可以尽快判断一些比较明显的错误的模式，节省时间:**

主要的思路：

首先设置两个列表分别存放的是各种括号的开括号和闭括号，然后遍历给定的字符串，分如下几种情况：

1.字符串 首字符 出现在闭括号列表中，直接结束，输出错误  
2.字符串长度不为偶数，直接结束，输出错误  
3.对原始字符串列表化去重，如果去重后的列表长度不为偶数直接结束，输出错误  
4.遍历字符串，将属于开括号集合的括号加入到列表中，当遇上一个闭括号的时候计算该闭括号在闭括号列表中的索引与  
当前列表最后一个开括号在开括号列表中的索引是否一致，一致则继续，否则直接结束，输出错误

def bracket_mathch(one_str):
        ''''' 括号匹配 '''
        tmp_list = []
        open_bracket_list = ['(', '[', '{', '<', '《']
        close_bracket_list = [')', ']', '}', '>', '》']
        one_str_list = list(one_str)
        length = len(one_str_list)
        set_list = list(set(one_str_list))
        num_list = [one_str_list.count(one) for one in set_list]
        if one_str[0] in close_bracket_list:
            return False
        elif length % 2 != 0:
            return False
        elif len(set_list) % 2 != 0:
            return False
        else:
            for i in range(length):
                if one_str[i] in open_bracket_list:
                    tmp_list.append(one_str[i])
                elif one_str[i] in close_bracket_list:
                    if close_bracket_list.index(one_str[i]) == open_bracket_list.index(tmp_list[-1]):
                        tmp_list.pop()
                    else:
                        return False
                        break
        return True
    
    if __name__ == '__main__':
        one_str_list = ['({})', '({[<《》>]})', '[(]){}', '{ { { { { {', '([{}])', '}{[()]']
        for one_str in one_str_list:
            if bracket_mathch(one_str):
                print(one_str, '正确')
            else:
                print(one_str, '错误')
    
        tmp = '{}[{()()[]<{ {[[[[(())()()(){}[]{}[]()<>]]]]}}>}]'
        print(bracket_mathch(tmp))

猜你喜欢

使用 Amazon Elastic Inference 降低 Amazon SageMaker PyTorch 模型的机器学习推理成本
Python代码风格总结
java内存区域
使用 Amazon SageMaker 加速自定义 AI 医疗影像算法构建
Java——Volatile关键字
Java直接调用Python
第三部分 SAP on AWS HA Single AZ
Java泛型
Python3：range()函数
基于 Amazon SageMaker 进行汽车型号的图像识别——一个基于深度学习迁移学习的端到端图像分类器
Python3 isinstance() 函数
Java之反射
使用 Amazon SageMaker 构建基于 gluon 的推荐系统
Python 学习 --- 基础知识
Java动态代理
Java面试经
使用 Amazon SageMaker 运行基于 TensorFlow 的中文命名实体识别
使用 DeepAR 进行时间序列预测
python：面向对象初级
Java数组（二）

zl程序教程

当前栏目

python实现括号匹配

相关文章