算法面试题——给定一个只包括 ‘(‘，‘)‘，‘{‘，‘}‘，‘[‘，‘]‘ 的字符串 s ，判断字符串是否有效。

深藏阁楼爱情的钟 2024-04-03 09:24 55阅读 0赞

![在这里插入图片描述][f23705c3fb9241599b0eed71b74bc5ab.jpeg_pic_center]

--------------------

## **给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。** ##

**有效字符串需满足：**

> **左括号必须用相同类型的右括号闭合。  
> 左括号必须以正确的顺序闭合。  
> 每个右括号都有一个对应的相同类型的左括号。**

> **示例 1：  
> 输入：s = “()”  
> 输出：true  
> 示例 2：  
> 输入：s = “()\[\]\{\}”  
> 输出：true  
> 示例 3：  
> 输入：s = “(\]”  
> 输出：false**

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/valid-parentheses

> **思路：  
> 遍历字符串  
> 遇到左边括号，就入栈  
> 遇到右边括号，就弹出栈顶  
> 为空——》False  
> 不为空——》弹出栈顶元素  
> 栈顶元素和遇到的右边的括号匹配一下，看是否是相同类型  
> 是不同类型就返回False  
> 是相同类型就继续向下遍历  
> 如果字符串全部匹配完了  
> 栈为空 – True  
> 占不为空 – False**

## 创建栈 ##

class Stack:
        def __init__(self):
            # 把列表的最后一个元素作为栈顶
            self.__data = []
    
        def push(self, item):
            # 添加一个元素到栈顶
            # append insert
            self.__data.append(item)
    
        def pop(self):
            # 要判断栈是否为空
            if self.is_empty():
                raise ValueError('栈为空')
            return self.__data.pop()
    
        def top(self):
            # 要判断栈是否为空
            if self.is_empty():
                raise ValueError('栈为空')
            return self.__data[-1]
    
        def is_empty(self):
            return self.__data == []
    
        def size(self):
            return len(self.__data)

from stack01 import Stack
    def func(string):
        if len(string)%2:
            return False
        stack=Stack()
        dic={
        
            '(':')',
            '[':']',
            '{':'}'
        }
        for char in string:
            #todo 判断遇到的是左括号还是右括号
            if char in '([{':
                stack.push(dic[char])
            else:
                if stack.is_empty() or stack.pop()!=char:
                    return False
        return stack.is_empty()
    
    if __name__ == '__main__':
        print(func('{([])}'))

--------------------

![在这里插入图片描述][a26ecbd16a5241d99235fc55eb81b575.jpeg_pic_center]

[f23705c3fb9241599b0eed71b74bc5ab.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/94e1d5aabcb149d6834edf18ffae2380.jpeg
[a26ecbd16a5241d99235fc55eb81b575.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d05000b1f47a47ec815fb272df26a056.jpeg