代码随想录07：栈与队列

栈与队列

• 栈：先进后出
• 队列：先进先出

栈用于处理匹配问题文章源自十年又十年-https://www.bbigsun.com/413.html

有效的括号

问题描述：给定一个只包含 '('、')'、'['、']'、'{'、'}' 的字符串，判断是否有效文章源自十年又十年-https://www.bbigsun.com/413.html

• 左括号必须和右括号匹配
• 左括号必须以正确的顺序闭合
• 空字符串有效

思路：先分析可能存在的情况，遇见左括号入栈，遇见匹配的右括号出栈文章源自十年又十年-https://www.bbigsun.com/413.html

• 当左边括号多的时候 '(()'，栈内会剩余 '('，无法匹配
• 当右边括号多的时候 '())'，栈内没有括号，栈外存在右括号，无法匹配
• 当左右括号不匹配的时候'(]'，栈内的括号不匹配栈外的括号，无法匹配

def is_true(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(')')
        elif i == '[':
            stack.append(']')
        elif i == '{':
            stack.append('}')
        elif not stack or stack[-1] != i:
            return False
        else:
            stack.pop()
    return True if not stack else False

逆波兰表达式求值

问题描述：根据逆波兰表示法，求表达式的值文章源自十年又十年-https://www.bbigsun.com/413.html

输入：[2,1,+,3,*]
输出：9文章源自十年又十年-https://www.bbigsun.com/413.html

思路：遇见数字则入栈，遇见运算符则取出两个数字运算后入栈。文章源自十年又十年-https://www.bbigsun.com/413.html 文章源自十年又十年-https://www.bbigsun.com/413.html