概念

教科书对stack / queue 一般都会同时进行介绍, 同时记忆比较好记.
stack 是后进先出. 后面进来的元素, 弹出的时候反而先走.
queue 是排队(所以中文翻译成队列) , 先进先出. 可以想象成排队买游戏机的人, 喊到他了就高高兴兴交钱去了.

图示

stack 可以用洗碗这个场景来记忆. 洗碗的时候, 我们都是一边洗一边把碗叠起来, 如下图:

碗全部洗完之后, 要把它们挪到柜子里. 之前越是靠后的碗, 越是先被挪走, 如下图:

很好记.

主要操作

增加元素, 弹出元素, 似乎没什么特别可说的? 如果用C/Java 实现会涉及到"幽灵内存"问题. 不过现在编程一般都是直接使用语言本身内建的数据结构, 所以作为一个不需要考试的中年人, 我就不用C/Java 来写了, 偷懒用Python.

代码

class MyStack:"""用python实现stack 会少了个很重要的概念: capacity resize , 因为python本身的list 是动态数组, 不需要处理扩容."""def __init__(self):self.data_list = []def get_size(self):return len(self.data_list)def push(self, data):self.data_list.append(data)def pop(self):if self.get_size() < 1:return Nonereturn self.data_list.pop()# 查看当前对象(即最后一个), 但不删除def peek(self):if self.get_size() < 1:return Nonereturn self.data_list[-1]def is_empty(self):return self.get_size() < 1def __repr__(self):return self.data_list.__str__()

python的list 其实已经实现了stack的功能, 所以这个代码真是偷懒到极致啊.

回答年轻时候的疑惑

在学校学习数据结构的时候, 我一直不太明白既然很多现代编程语言已经有了这些数据结构, 为什么我们要重写一遍? 现在, 我穿越回去告诉自己:

从"以后项目是否会需要自己手写这些最基础的数据结构" 这个角度来看, 没有必要. 重写一遍的目的, 是让大脑记下动手的经验, 让自己对相关知识的记忆更牢靠. 很多概念如果只是死记硬背不动手, 很快就会忘记.

另一个原因是, 在java/python这类语言里都实现了动态列表, 内存的分配不用你管, 所以用来写数据结构比较方便, 但不利于了解指针和内存泄露这些概念. 如果想让基础更扎实,那么最好重写一遍.

<算法4> 这本书里有java实现的stack, 也提到了幽灵内存的概念, 所以java版本就不写了. 在最后写完python会再写个C版本练练手.

应用-计算表达式

在很多实际应用中, 用stack 处理会达到很巧妙的类似魔法的效果. 这里举3个应用的例子: 实现计算表达式, 迷宫闯关和遍历树. 遍历树会在后面再写, 这里就写计算表达式.

这个例子是从<算法4> 这本书看来的, 当时拍案叫絕啊. 结果自己用python默写出来又翻车了.

需求

写一个程序, 能够计算以下3个字符串表达式的结果:

1. 15 + 21
2. 8 * ( 11 - ( 7 + ( 3 + 5 ) ) )

有问题的代码

#! /usr/bin/python
# -*- coding: UTF-8 -*-"""作者: 小肥巴巴简书: https://www.jianshu.com/u/db796a501972邮箱: imyunshi@163.comgithub: https://github.com/xiaofeipapa/algo_example您可以任意转载, 恳请保留我作为原作者, 谢谢."""
from stack_v_1 import MyStackdef cal_each(before, last, opt):before = float(before)last = float(last)if opt == '+':return before + lastelif opt == '-':return before - lastelif opt == '*':return before * lastelif opt == '/':return before / lastelse:raise Exception('不支持的操作: ', opt)def calculator(input_str):"""计算 数值表达式:param input_str::return:"""opt_list = ['+', '-', '*', '/']opt_box = MyStack()  # 存放操作符val_box = MyStack()  # 存放值step = 0for i in range(0, len(input_str)):val = input_str[i].strip()if not val:continue"""运算规则, 当val 是 ) 时, 舍弃进入下一个循环当val 是 ) 开始计算当val 是操作符或者值时, 进入各自的stack更详细见图形分析"""if val == '(':passelif val in opt_list:opt_box.push(val)elif val == ')':# 开始计算, 弹出最近的操作符, 最近的两个数opt = opt_box.pop()"""1) 弹出的先后顺序很重要, 应该后入的在后(减法和除法都是从左到右)2) 不能用 python的eval, 否则就没达到锻炼目的"""last = val_box.pop()before = val_box.pop()result = cal_each(before, last, opt)if val_box.is_empty():print('--- 计算结果: ', result)return result# 否则推到stack 里准备下一个运算val_box.push(result)else:# 正常的值, 推入val_box.push(val)step += 1print('--- 第 %d 步: ' % step)print('--- val_box: ', val_box)print('--- opt_box: ', opt_box)print('\n\n')# -------- end forraise Exception('不可能到这里, 程序设计有问题')def test_it():str_1 = '8 * ( 11 - ( 7 + ( 3 + 5 ) ) )'calculator(str_1)# 意外"惊喜": 这个程序不识别11, 如何识别多位数?# 需要先对表达式进行一次扫描.if __name__ == '__main__':test_it()

代码解说

在python里, 其实直接 eval 就可以计算, 不过既然是练习当然要自己动手. 而且练熟了这种思路会对以后工作很有帮助. 举个例子, 某个生产厂希望你能写一个简单的规则程序, 实现有限的操作指令的组合, 达到"智能"的效果. 这类规则程序的算法一般就是计算器的算法改动版.

在这个算法实现里, 原书作者巧妙地用两个stack 分别保存操作符和计算值. 我在代码里加了print, 可以一步步看到两个stack 是怎么一步步存储数据的:

# 待计算的表达式:  8 * ( 11 - ( 7 + ( 3 + 5 ) ) )--- 第 1 步: 
--- val_box:  ['8']
--- opt_box:  []--- 第 2 步: 
--- val_box:  ['8']
--- opt_box:  ['*']--- 第 3 步: 
--- val_box:  ['8']
--- opt_box:  ['*']--- 第 4 步: 
--- val_box:  ['8', '1']
--- opt_box:  ['*']

在值的检查判断里, 左括号"(" 是被省略的, 右括号才是真正计算的开始:

elif val == ')':# 开始计算, 弹出最近的操作符, 最近的两个数opt = opt_box.pop()"""1) 弹出的先后顺序很重要, 应该后入的在后(减法和除法都是从左到右)2) 不能用 python的eval, 否则就没达到锻炼目的"""last = val_box.pop()before = val_box.pop()result = cal_each(before, last, opt)if val_box.is_empty():print('--- 计算结果: ', result)return result# 否则推到stack 里准备下一个运算val_box.push(result)

当遇到右括号的时候, 从值stack 连续弹两个数出来进行, 操作符opt_stack里弹一个操作符, 三者进行操作. 由于stack 是后进先出的特性, 所以这个计算必然是最内层(靠右)的计算. 操作完之后, 压回到stack, 下次再弹出的必然也是它, 符合需求.

翻车在哪

思路没有问题, 那么这段程序翻车在哪? 主要在两个地方:

1. 原书里, 所有表达式的输入用命令行进行, 所以可以确保每一次输入都是完整的数字. 当我把输入放在字符串的时候, 数字 11 被循环拆分为两个1进行计算, 导致了bug.
2. 在弹出值进行操作的时候只考虑到二元操作符, 所以每次都弹两个值. 类似 sqrt 这种一元操作符, 其实只需要一个值.

解决办法: 第二个问题好解决, 麻烦的是第一个. 但是我想了想还是解决吧, 太多算法的示例像是玩具, 还不如在复习算法的时候就写点实用代码.

修改版

修改版如下:

#! /usr/bin/python
# -*- coding: UTF-8 -*-"""作者: 小肥巴巴简书: https://www.jianshu.com/u/db796a501972邮箱: imyunshi@163.comgithub: https://github.com/xiaofeipapa/algo_example您可以任意转载, 恳请保留我作为原作者, 谢谢."""
from my_statck import MyStack
import mathdef handle_temp_value(opt_box, temp_opt, val_box, temp_value):# 处理数值if len(temp_value) > 0:val_box.push(''.join(temp_value))temp_value.clear()# 处理操作符if len(temp_opt):opt_box.push(''.join(temp_opt))temp_opt.clear()def cal_each(opt_box, val_box):"""1) 弹出的先后顺序很重要, 应该后入的在后(减法和除法都是从左到右)2) 不能用 python的eval, 否则就没达到锻炼目的"""opt = opt_box.pop()if opt not in ['+', '-', '*', '/', 'sqrt']:raise Exception('不支持的操作: ', opt)# 弹出最近的数last = float(val_box.pop())if opt == 'sqrt':result = math.sqrt(last)else:# 弹出前一个数before = float(val_box.pop())if opt == '+':result = before + lastelif opt == '-':result = before - lastelif opt == '*':result = before * lastelse:result = before / lastval_box.push(result)return resultdef calculator(input_str):"""计算 数值表达式:param input_str::return:"""opt_list = ['+', '-', '*', '/']opt_box = MyStack()         # 存放操作符val_box = MyStack()         # 存放值# 增加两个容器来处理多位数和操作符temp_value = list()         # 临时容器, 保存多位数temp_opt = list()           # 临时容器, 保存字符串step = 0for i in range(0, len(input_str)):val = input_str[i].strip()if not val:continue"""运算规则, 当val 是 ) 时, 舍弃进入下一个循环当val 是 ) 开始计算当val 是操作符或者值时, 进入各自的stack更详细见图形分析"""# 先处理数值. 数值有可能是小数if val == '.' or val.isdigit():temp_value.append(val)elif val.isalpha():temp_opt.append(val)else:# 处理临时数据handle_temp_value(opt_box, temp_opt, val_box, temp_value)if val == '(':passelif val in opt_list:opt_box.push(val)elif val == ')':result = cal_each(opt_box, val_box)step += 1# print('--- 第 %d 步: ' % step)# print('--- val_box: ', val_box)# print('--- opt_box: ', opt_box)# print('\n\n')# -------- end for# 处理临时数据handle_temp_value(opt_box, temp_opt, val_box, temp_value)if opt_box.is_empty():result = val_box.pop()else:while not opt_box.is_empty():result = cal_each(opt_box, val_box)print('==== 最终计算结果: %0.4f' % result)def test_it():str_1 = '8 * ( 11 - ( 7 + ( 3 + 5 ) ) )'calculator(str_1)str_1 = ' 15 + sqrt(9) - (20 + 2 )'calculator(str_1)str_1 = ' 15 + 21'calculator(str_1)if __name__ == '__main__':test_it()

修改版多考虑了两个场景:

1. 计算值可能是多位数据, 所以要加一个临时容器进行处理.
2. 操作符也有可能是单词而不是加减乘除单个字符, 所以也要加个容器处理.

这样设计的好处是一边扫描字符串一边进行计算, 效率高, 不好的地方是难以扩展: 如果用户的输入不规范怎么办? 怎么先进行处理? 是不是又要在主程序里加一堆变量?

所以更好的做法是将主程序拆分成两部分: 一部分进行数据清洗, 确认数据没有问题. 另一部分进行逻辑计算. 不过这已经涉及到具体业务, 而不是复习算法了, 就有待各位自己把玩了.

写首歪诗来记住

程序员的特点是一周之后会忘记自己的代码. 一大段程序就像一大段文章, 原封不动记下来是不可能的, 所以要提炼并记忆一些要点, 根据这些优点复写其他部分. (想想大厂面试要手写算法, 还是有点道理的)

于是乎, 献上歪诗一首:

清洗识别多位数,    # 清洗数据, 识别一元操作符和单词操作符
两个容器放在前.    # 用两个stack 分别记录操作符和值
右括号才是计算.    # 遇到)才开始计算
弹值顺序有先后.    # 某些操作符有顺序要求, 先谈哪个值很重要

搞定!