鱼C论坛

 找回密码
 立即注册
查看: 1419|回复: 1

[技术交流] python基本数据结构类型--栈的应用

[复制链接]
发表于 2020-3-31 17:43:53 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
北大地空《数据结构与算法》笔记 by dlnb526
2020.3
本文中的代码来自课程页面。


在上一篇笔记中,学习了栈的相关概念。
python基本数据结构类型--初识栈
https://fishc.com.cn/thread-162801-1-1.html
(出处: 鱼C论坛)

在这篇笔记中我记录了利用栈来实现的两个功能,主要是加深对栈概念的理解。


                               
登录/注册后可看大图


首先回顾之前栈的建立
  1. # Bradley N. Miller, David L. Ranum
  2. # Introduction to Data Structures and Algorithms in Python
  3. # Copyright 2005
  4. #
  5. #stack.py

  6. class Stack:
  7.     def __init__(self):
  8.         self.items = []

  9.     def isEmpty(self):
  10.         return self.items == []

  11.     def push(self, item):
  12.         self.items.append(item)

  13.     def pop(self):
  14.         return self.items.pop()

  15.     def peek(self):
  16.         return self.items[len(self.items)-1]

  17.     def size(self):
  18.         return len(self.items)

复制代码

在上面我们通过列表的方式实现了栈的种种操作方式。
下面的代码实现都需要先实现这个类。

栈的应用--括号匹配
在学习一些数学知识之后我们就知道在一个计算的式子中,括号中的内容优先级是最高的,如果我们要自己去实现一个计算的过程,就必须把各种符号以及括号的优先级弄明白。

首先,我们知道括号的规则是成对出现,也就是说出现了左括号一定有一个对应的右括号,除此之外还需要满足每队开闭括号要有正确的嵌套,像(()(()) 这样的括号就是错误的,原因在于最左边的括号没有对应的闭括号。

在了解到了这些最基本的内容之后,我们来开括号是如何实现的。
假设我们从左到右去数,不断地出现左括号和右括号,最新出现的左括号一定对应紧接着其最新出现的右括号,而更久之前就出现的左括号回再之后才匹配到,这正好对应了我们在栈中的情形--在栈顶最先放上去的项先被弹出匹配,而被压在下面的项要在后面才能重见天日。

  1. def parChecker(symbolString):
  2.     s = Stack()
  3.     balanced = True   #判断左右括号数量最终是否匹配
  4.     index = 0
  5.     while index < len(symbolString) and balanced:
  6.         symbol = symbolString[index]
  7.         if symbol == "(":
  8.             s.push(symbol)#当遇到左括号,先把它压入栈
  9.         else:
  10.             if s.isEmpty():
  11.                 balanced = False#如果提前就空了,肯定就是不匹配了
  12.             else:
  13.                 s.pop()

  14.         index = index + 1

  15.     if balanced and s.isEmpty():
  16.         return True
  17.     else:
  18.         return False

  19. print(parChecker('((()))'))
  20. print(parChecker('(()'))
复制代码
  1. True
  2. False
复制代码

当然了,除了小括号()之外,我们在学习数学的时候还遇见过中括号和大括号。

这个时候我们还要考虑匹配的情况。比如这样的([)]显然就是不匹配的!

  1. def parChecker(symbolString):
  2.     s = Stack()
  3.     balanced = True
  4.     index = 0
  5.     while index < len(symbolString) and balanced:
  6.         symbol = symbolString[index]
  7.         if symbol in "([{":
  8.             s.push(symbol)
  9.         else:
  10.             if s.isEmpty():
  11.                 balanced = False
  12.             else:
  13.                 top = s.pop()
  14.                 if not matches(top,symbol):
  15.                        balanced = False
  16.         index = index + 1
  17.     if balanced and s.isEmpty():
  18.         return True
  19.     else:
  20.         return False

  21. def matches(open,close):#这里检查是否匹配
  22.     opens = "([{"
  23.     closers = ")]}"
  24.     return opens.index(open) == closers.index(close)#巧妙地利用索引是否相同,省去了判断的步骤
  25.    

  26. print(parChecker('{{([][])}()}'))
  27. print(parChecker('[{()]'))
复制代码
  1. True
  2. False
复制代码

栈的应用--进制转换
所谓的“进制”就是用多少个字符来表示整数。
十进制是0~9这十个数字字符,二进制是0、1两个字符
我们经常需要将整数在二进制和十进制之间转换
如:十进制数233 其实是2*10^2+3*10^1+3*10^0,它对应的二进制数为11101001,1×2^7+1×2^6+1×2^5+0×2^4+1×2^3+0×2^2+0×2^1+1×2^0

“除以2”的过程,得到的余数是从低到高的次序,而输出则是从高到低,所以需要一个栈来反转次序。

                               
登录/注册后可看大图

(图片来自知乎)

我们可以从上面的图里面看到,对29进行操作是从上向下的,而最后的结果确实从下到上的字符串排列。
除了二进制,转换为其他进制也是相同的原理。

  1. def baseConverter(decNumber,base):#这里的base就是要转换成的进制,后面我们会看到他作为除数出现。
  2.     digits = "0123456789ABCDEF"#这里一直到了十六进制的最后一个字符

  3.     remstack = Stack() #这里是建立一个空栈

  4.     while decNumber > 0:
  5.         rem = decNumber % base
  6.         remstack.push(rem)
  7.         decNumber = decNumber // base

  8.     newString = ""
  9.     while not remstack.isEmpty():
  10.         newString = newString + digits[remstack.pop()]

  11.     return newString
  12. ##实验:
  13. print(baseConverter(25,2))
  14. print(baseConverter(25,16))
复制代码
  1. 11001
  2. 19
复制代码




                               
登录/注册后可看大图


上面就是在课程中关于栈的应用的全部内容了。

评分

参与人数 1贡献 +2 收起 理由
zltzlt + 2 鱼C有你更精彩^_^

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2020-3-31 17:47:06 | 显示全部楼层
支持!!
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-9 19:34

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表