|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
北大地空《数据结构与算法》笔记 by dlnb526
2020.3
本文中的代码来自课程页面。
在上一篇笔记中,学习了栈的相关概念。
python基本数据结构类型--初识栈
https://fishc.com.cn/thread-162801-1-1.html
(出处: 鱼C论坛)
在这篇笔记中我记录了利用栈来实现的两个功能,主要是加深对栈概念的理解。
首先回顾之前栈的建立
- # Bradley N. Miller, David L. Ranum
- # Introduction to Data Structures and Algorithms in Python
- # Copyright 2005
- #
- #stack.py
- class Stack:
- def __init__(self):
- 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)
复制代码
在上面我们通过列表的方式实现了栈的种种操作方式。
下面的代码实现都需要先实现这个类。
栈的应用--括号匹配
在学习一些数学知识之后我们就知道在一个计算的式子中,括号中的内容优先级是最高的,如果我们要自己去实现一个计算的过程,就必须把各种符号以及括号的优先级弄明白。
首先,我们知道括号的规则是成对出现,也就是说出现了左括号一定有一个对应的右括号,除此之外还需要满足每队开闭括号要有正确的嵌套,像(()(()) 这样的括号就是错误的,原因在于最左边的括号没有对应的闭括号。
在了解到了这些最基本的内容之后,我们来开括号是如何实现的。
假设我们从左到右去数,不断地出现左括号和右括号,最新出现的左括号一定对应紧接着其最新出现的右括号,而更久之前就出现的左括号回再之后才匹配到,这正好对应了我们在栈中的情形--在栈顶最先放上去的项先被弹出匹配,而被压在下面的项要在后面才能重见天日。
- def parChecker(symbolString):
- s = Stack()
- balanced = True #判断左右括号数量最终是否匹配
- index = 0
- while index < len(symbolString) and balanced:
- symbol = symbolString[index]
- if symbol == "(":
- s.push(symbol)#当遇到左括号,先把它压入栈
- else:
- if s.isEmpty():
- balanced = False#如果提前就空了,肯定就是不匹配了
- else:
- s.pop()
- index = index + 1
- if balanced and s.isEmpty():
- return True
- else:
- return False
- print(parChecker('((()))'))
- print(parChecker('(()'))
复制代码
当然了,除了小括号()之外,我们在学习数学的时候还遇见过中括号和大括号。
这个时候我们还要考虑匹配的情况。比如这样的([)]显然就是不匹配的!
- def parChecker(symbolString):
- s = Stack()
- balanced = True
- index = 0
- while index < len(symbolString) and balanced:
- symbol = symbolString[index]
- if symbol in "([{":
- s.push(symbol)
- else:
- if s.isEmpty():
- balanced = False
- else:
- top = s.pop()
- if not matches(top,symbol):
- balanced = False
- index = index + 1
- if balanced and s.isEmpty():
- return True
- else:
- return False
- def matches(open,close):#这里检查是否匹配
- opens = "([{"
- closers = ")]}"
- return opens.index(open) == closers.index(close)#巧妙地利用索引是否相同,省去了判断的步骤
-
- print(parChecker('{{([][])}()}'))
- print(parChecker('[{()]'))
复制代码
栈的应用--进制转换
所谓的“进制”就是用多少个字符来表示整数。
十进制是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进行操作是从上向下的,而最后的结果确实从下到上的字符串排列。
除了二进制,转换为其他进制也是相同的原理。
- def baseConverter(decNumber,base):#这里的base就是要转换成的进制,后面我们会看到他作为除数出现。
- digits = "0123456789ABCDEF"#这里一直到了十六进制的最后一个字符
- remstack = Stack() #这里是建立一个空栈
- while decNumber > 0:
- rem = decNumber % base
- remstack.push(rem)
- decNumber = decNumber // base
- newString = ""
- while not remstack.isEmpty():
- newString = newString + digits[remstack.pop()]
- return newString
- ##实验:
- print(baseConverter(25,2))
- print(baseConverter(25,16))
复制代码
上面就是在课程中关于栈的应用的全部内容了。 |
评分
-
查看全部评分
|