python实现括号匹配的多种方法小结_Python

一.方法1

在一些场景下会用到括号匹配的情况,通常用栈来实现,通过栈和函数封装来实现

class stack:
    def __init__(self):
        # 我们定义空列表，实现栈的进入进出操作
        self.items = []
 
    def isempty(self):
        # 判断是否为空栈
        return self.items == []
 
    def push(self, item):
        # 向栈中加入元素，新的元素自动加入栈底
        self.items.append(item)
 
    def pop(self):
        # 移出栈顶元素。
        return self.items.pop()
 
    def peek(self):
        # 返回栈顶元素
        return self.items[len(self.items) - 1]
 
    def size(self):
        # 返回栈的长度
        return len(self.items)
 
 
# 定义一个函数，用来检测括号是否匹配
def check(string):
    s = stack()  # 将前面定义的栈的类进行实例化
    class_equal = true  # 定义初始匹配度为true
    index = 0
    while index < len(string) and class_equal:
        test_str = string[index]
        # 当字符串是‘（'，则压入栈中
        if test_str == '(':
            s.push(test_str)
        else:
            # 如果当前字符串是')'，且栈中没有元素，说明不匹配
            if s.isempty():
                class_equal = false
            else:
                # 如果栈不为空，那么去掉一个栈中的'('，表示有一对括号已匹配
                s.pop()
        index += 1
 
    if class_equal and s.isempty():
        return '所有括号匹配'
    else:
        return '不匹配'
 
 
print(check('((()))'))
print(check('()()))'))

二.方法2

加入一些自主的输入使得变得更加的自由，有了参与感

class stack:
    def __init__(self):
        self.items = []  # 使用列表来存储栈中的元素
 
    def push(self, item):
        self.items.append(item)  # 将元素压入栈顶
 
    def pop(self):
        if not self.is_empty():
            return self.items.pop()  # 弹出栈顶元素
        else:
            raise indexerror("pop from empty stack")
 
    def peek(self):
        if not self.is_empty():
            return self.items[-1]  # 返回栈顶元素，但不弹出
        else:
            return none
 
    def is_empty(self):
        return len(self.items) == 0  # 检查栈是否为空
 
    def size(self):
        return len(self.items)  # 返回栈中元素的个数
 
 
def is_valid(expression, stack):
    mapping = {'{': '}', '[': ']', '(': ')'}
    for char in expression:
        # 判断是否为左括号
        if char in mapping.keys():
            stack.push(char)
        elif char in mapping.values():  # 判断是否为右括号
            if stack.is_empty() == false and mapping[stack.peek()] == char:
                stack.pop()
            else:
                return false
        else:
            continue
 
    return stack.size() == 0
 
 
expression = input("请输入包含括号的一系列字符串:\n")
 
stack = stack()
 
if is_valid(expression, stack):
    print("括号匹配成功")
else:
    print("括号匹配失败")

三.方法3

除了用栈外,也可以用逻辑判断来实现综合性的,第一种方式通过模拟栈的操作来检查括号匹配情况，第二种方式在进行一些基础判断后，同样根据括号对应关系来判断匹配与否。

def check(row):
    """
    check函数 用于检查给定字符串中括号是否正确匹配（第一种实现方式）。
    参数 row: 待检查括号匹配情况的字符串
    """
    # 存储左括号字符，用于第一种括号匹配实现方式
    open_brackets = '([{<'
    # 存储右括号字符，用于第一种括号匹配实现方式
    close_brackets = ')]}>'
    # 映射左右括号的字典，便于第一种括号匹配实现方式中出栈判断
    brackets_map = {')': '(', ']': '[', '}': '{', '>': '<'}
 
    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
    return label
 
 
def bracket_mathch(one_str):
    """
    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:
                # 判断当前闭括号与栈顶（tmp_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__':
 
    # 第一种实现方式的测试示例字符串
    rows = [
        '([<^>x[ ]{a}]{/}{t}g<^>)<{x}b>{x}<z({%}w >[b][c[c]]{{h}}',
        '[/]{((x)({{}}w)w){f}{v}[%(1{u}{ })([[ ]-]h)]{c}(*)[y]}',
        '<<(^)z>>[b]< >[[©u[v]{z<b< >>}]g]/b[(])v(v)(+)',
        '[[b]][(v)g]([{{<->+}e}[*]d<+>]g[[a] <+>(v){b}]){a}[u]'
    ]
    print("使用check函数进行括号匹配测试的结果：")
    for row in rows:
        print(f"字符串 '{row}' 的括号匹配结果：{check(row)}")
 
    # 第二种实现方式的测试示例字符串
    one_str_list = [
        '({})',
        '({[<《》>]})',
        '[(]){}',
        '{{{{{{',
        '([{}])',
        '}{[()]'
    ]
    print("\n使用bracket_mathch函数进行括号匹配测试的结果：")
    for one_str in one_str_list:
        print(f"字符串 '{one_str}' 的括号匹配结果：{bracket_mathch(one_str)}")