class Stack:
    def __init__(self):
        # 我們定義空列表，實現(xiàn)棧的進入進出操作
        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)
 
 
# 定義一個函數(shù)，用來檢測括號是否匹配
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('()()))'))

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)  # 返回棧中元素的個數(shù)
 
 
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("括號匹配失敗")

def check(row):
    """
    check函數(shù) 用于檢查給定字符串中括號是否正確匹配（第一種實現(xiàn)方式）。
    參數(shù) row: 待檢查括號匹配情況的字符串
    """
    # 存儲左括號字符，用于第一種括號匹配實現(xiàn)方式
    open_brackets = '([{<'
    # 存儲右括號字符，用于第一種括號匹配實現(xiàn)方式
    close_brackets = ')]}>'
    # 映射左右括號的字典，便于第一種括號匹配實現(xiàn)方式中出棧判斷
    brackets_map = {')': '(', ']': '[', '}': '{', '>': '<'}
 
    stack = []
    label = True
    for char in row:
        # 如果字符是左括號，將其加入棧（用列表模擬棧）
        if char in open_brackets:
            stack.append(char)
        elif char in close_brackets:
            # 如果棧為空，說明右括號出現(xiàn)時沒有對應的左括號，匹配錯誤
            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函數(shù) 用于檢查給定字符串中括號是否正確匹配（第二種實現(xiàn)方式）。
    參數(shù) 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
    # 如果字符串長度不是偶數(shù)，直接判定括號匹配錯誤
    elif length % 2!= 0:
        return False
    # 如果去重后的字符列表長度不是偶數(shù)，直接判定括號匹配錯誤
    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__':
 
    # 第一種實現(xiàn)方式的測試示例字符串
    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)]){a}[u]'
    ]
    print("使用check函數(shù)進行括號匹配測試的結(jié)果：")
    for row in rows:
        print(f"字符串 '{row}' 的括號匹配結(jié)果：{check(row)}")
 
    # 第二種實現(xiàn)方式的測試示例字符串
    one_str_list = [
        '({})',
        '({[<《》>]})',
        '[(]){}',
        '{{{{{{',
        '([{}])',
        '}{[()]'
    ]
    print("\n使用bracket_mathch函數(shù)進行括號匹配測試的結(jié)果：")
    for one_str in one_str_list:
        print(f"字符串 '{one_str}' 的括號匹配結(jié)果：{bracket_mathch(one_str)}")