代码随想录07:栈与队列

BBigSun 评论192阅读模式

代码随想录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

纸上得来终觉浅,绝知此事要躬行。

weinxin
17688689121
我的微信
微信扫一扫
BBigSun
  • 本文由 BBigSun 发表于 2023年 3月 31日 08:28:13
  • 转载请务必保留本文链接:https://www.bbigsun.com/413.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定