- 学习了《Python Data Structure》的 3.1~3.9
- 和青软初步定了8月8号~8月12号的 5天 Python 内训
- 装了电风扇
- 写公众号
- 总结没有写,时间不够,因为看了电视剧
Tech
- 掌握了栈的定义、基本应用、使用python构造栈
线性结构
- 数据项之间的顺序由增加或删除的顺序决定的数据结构,称线性数据结构
栈
- 先进后出,LIFO
- 添加或删除项都发生在顶部,入口即出口
- 栈的作用:能反转项的顺序(浏览网页时候的后退)
- 使用python,实现了自定义的Stack,具有如下几个方法
is_empty()
push()
pop()
peek()
size()
用栈对括号匹配进行检查
- 栈里存 “(“,遇到 “)” 就
Stack.pop()
- 如果当前符号是 “)” ,且
Stack.is_empty()
,则不匹配,即可退出 - 若最后存在标志位为True,且栈为空,则括号匹配检查成功
- 复杂括号匹配,使用
"([{".index("(")
的方法对当前符号进行检查,
十进制转二进制
- 十进制转二进制采用“除2取余法”,由于最后的余数是二进制最左边的那个数,所以可以使用栈。
- 数字^10 % 2 结果push 到 Stack 中去
''.join(Stack.pop())
- 如果将十进制换成任意进制的数字,则添加一个digits参照表:
digits = '0123456789ABCDEF'
,每次 pop 出来的数字采用digits[Stack.pop()]
进行转换
中缀(Infix)/前缀(Prefix)/后缀(Postfix)
- 掌握中缀/前缀/后缀表达式的定义及转换
- 中缀:A + B * C
- 前缀:+A*BC
- 后缀:ABC*+
- 中缀:A + B * C
- 中缀转后缀
- 把字符串split成列表,初始化一个Stack
- 通过一个优先级字典
priority = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
,来判断字符和操作符的入栈顺序 - 若”(“,则直接入栈
- 若”)”,循环
Stack.pop()
,出来的不是 “(“,就追加到结果中去,否则退出循环 - 若”*/+-“,若Stack不为空,且Stack.peek() >= 当前操作符的优先级,则append到结果中去,再把当前操作符push到Stack中,否则直接push到Stack中
- 循环结束后,若Stack不为空,则循环pop,并append到结果中
''.join(ret)
- 计算后缀
- 若是[0-9],则push到Stack中去
- 若是操作符,则从Stack中pop出2个,与操作符进行计算,计算顺序为第二个pop出来的数字 操作符 第一个pop出来的数字