python基本数据结构类型--栈的应用

dlnb526

北大地空《数据结构与算法》笔记 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. 
   
7. class Stack:
   
8.     def __init__(self):
   
9.         self.items = []
   
10. 
    
11.     def isEmpty(self):
    
12.         return self.items == []
    
13. 
    
14.     def push(self, item):
    
15.         self.items.append(item)
    
16. 
    
17.     def pop(self):
    
18.         return self.items.pop()
    
19. 
    
20.     def peek(self):
    
21.         return self.items[len(self.items)-1]
    
22. 
    
23.     def size(self):
    
24.         return len(self.items)
    
25. 
    

复制代码

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

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

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

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

1. 
   
2. def parChecker(symbolString):
   
3.     s = Stack()
   
4.     balanced = True   #判断左右括号数量最终是否匹配
   
5.     index = 0
   
6.     while index < len(symbolString) and balanced:
   
7.         symbol = symbolString[index]
   
8.         if symbol == "(":
   
9.             s.push(symbol)#当遇到左括号，先把它压入栈
   
10.         else:
    
11.             if s.isEmpty():
    
12.                 balanced = False#如果提前就空了，肯定就是不匹配了
    
13.             else:
    
14.                 s.pop()
    
15. 
    
16.         index = index + 1
    
17. 
    
18.     if balanced and s.isEmpty():
    
19.         return True
    
20.     else:
    
21.         return False
    
22. 
    
23. print(parChecker('((()))'))
    
24. 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. 
    
22. def matches(open,close):#这里检查是否匹配
    
23.     opens = "([{"
    
24.     closers = ")]}"
    
25.     return opens.index(open) == closers.index(close)#巧妙地利用索引是否相同，省去了判断的步骤
    
26.    
    
27. 
    
28. print(parChecker('{{([][])}()}'))
    
29. 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. 
   
2. def baseConverter(decNumber,base):#这里的base就是要转换成的进制，后面我们会看到他作为除数出现。
   
3.     digits = "0123456789ABCDEF"#这里一直到了十六进制的最后一个字符
   
4. 
   
5.     remstack = Stack() #这里是建立一个空栈
   
6. 
   
7.     while decNumber > 0:
   
8.         rem = decNumber % base
   
9.         remstack.push(rem)
   
10.         decNumber = decNumber // base
    
11. 
    
12.     newString = ""
    
13.     while not remstack.isEmpty():
    
14.         newString = newString + digits[remstack.pop()]
    
15. 
    
16.     return newString
    
17. ##实验：
    
18. print(baseConverter(25,2))
    
19. print(baseConverter(25,16))

复制代码

1. 11001
   
2. 19

复制代码

                               
登录/注册后可看大图

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

Hello.

支持！！