python算法与数据结构DAY01(最全注释)

栈

基础

1. 满足LIFO(last-in-first-out，后进先出)
2. 具有反转特性

案例

1. 匹配括号

"""
对于给定（（（））（）（））来判断括号是否匹配
"""
from pythonds.basic import Stack
a = '((())()()())'
s = Stack()
i = 0#索引
matches = True#保证第一个是左括号
while i<len(a) and matches:
    if a[i] == '(':
        s.push(a[i])#左括号就加入
    else:
        if s.isEmpty():#如果第一不是左括号直接失败
            matches = False
        else:
            s.pop()#遇见右括号就删除左括号
    i +=1
if matches and s.isEmpty():#最终栈是空的
    print('True')
else:
    print('False')

2. 匹配符号

from pythonds.basic import Stack
s = Stack()
a = '({}}{{}[][]))()'
matches = True
i = 0
while i<len(a) and matches:
    if a[i] == '({[':
        s.push(a[i])#遇见左符号就入栈
    else:
        if s.isEmpty():#遇见右符号栈空，直接不匹配
            matches = False
        else:
            top = s.top()
            if '({['.index(a[i]) != ')}]'.index(top):#判断最后入栈的与接下来的右符号是否相等
                matches = False#不相等就不匹配
    i +=1
if matches and s.isEmpty():#最终栈空
    print('true')
else:
    print('false')
       

3. 十进制转二进制

"""
十进制转二进制，可以采取除2取余法。结果为余数逆向排序。符合反转特性
"""

from pythonds.basic import Stack
a = 233
print("{:b}".format(a))#利用format方法打印其二进制
s = Stack()
while a>0:
    rem = a%2#取余
    s.push(rem)#余数入栈
    a = a//2#整除
resultStr = ''
while not s.isEmpty():#相当于遍历
    resultStr = resultStr+str(s.pop())#取出栈中数字
print(resultStr)

4. 十进制转任意进制

from pythonds.basic import Stack
a = 233
print("{:x}".format(a))#16进制输出
def change(num,base):
	#string = '0123456789abcdef'
    s = Stack()
    while num>0:
        rem = num%base
        s.push(rem)
        num = num//base

    resultStr = ''
    while not s.isEmpty():
        resultStr = resultStr+str(s.pop())
        #resultStr = resultStr+string[(s.pop())]
    return resultStr

print(change(a,16))
-------------------------------
e9
149
这显然输出的不对，不过e对应的正好是14.加上如图注释版本就好了

如有错误，还望指正。评论区交流。