Python算法实战系列:栈

  1. 云栖社区>
  2. 博客>
  3. 正文

Python算法实战系列:栈

行者武松 2017-08-01 10:36:00 浏览811
展开阅读全文

栈(stack)又称之为堆栈是一个特殊的有序表,其插入和删除操作都在栈顶进行操作,并且按照先进后出,后进先出的规则进行运作。

如下图所示

例如枪的弹匣,第一颗放进弹匣的子弹反而在发射出去的时候是最后一个,而最后放入弹匣的一颗子弹在打出去的时候是第一颗发射出去的。

栈的接口

如果你创建了一个栈,那么那么应该具有以下接口来进行对栈的操作

知道栈需要上述的接口后,那么在Python中,列表就类似是一个栈,提供接口如下:

Python中的栈接口使用实例:


  1. # 创建一个栈 
  2.  
  3. In [1]: s = [] 
  4.  
  5. # 往栈内添加一个元素 
  6.  
  7. In [2]: s.append(1) 
  8.  
  9. In [3]: s 
  10.  
  11. Out[3]: [1] 
  12.  
  13. # 删除栈内的一个元素 
  14.  
  15. In [4]: s.pop() 
  16.  
  17. Out[4]: 1 
  18.  
  19. In [5]: s 
  20.  
  21. Out[5]: [] 
  22.  
  23. # 判断栈是否为空 
  24.  
  25. In [6]: not s 
  26.  
  27. Out[6]: True 
  28.  
  29. In [7]: s.append(1) 
  30.  
  31. In [8]: not s 
  32.  
  33. Out[8]: False 
  34.  
  35. # 获取栈内元素的数量 
  36.  
  37. In [9]: len(s) 
  38.  
  39. Out[9]: 1 
  40.  
  41. In [10]: s.append(2) 
  42.  
  43. In [11]: s.append(3) 
  44.  
  45. # 取栈顶的元素 
  46.  
  47. In [12]: s[-1] 
  48.  
  49. Out[12]: 3  

一大波实例

在了解栈的基本概念之后,让我们再来看几个实例,以便于理解栈。

括号匹配

题目

假如表达式中允许包含三中括号()、[]、{},其嵌套顺序是任意的,例如:

正确的格式


  1. {()[()]},[{({})}] 

错误的格式


  1. [(]),[()),(()} 

编写一个函数,判断一个表达式字符串,括号匹配是否正确

思路

  1. 创建一个空栈,用来存储尚未找到的左括号;
  2. 便利字符串,遇到左括号则压栈,遇到右括号则出栈一个左括号进行匹配;
  3. 在第二步骤过程中,如果空栈情况下遇到右括号,说明缺少左括号,不匹配;
  4. 在第二步骤遍历结束时,栈不为空,说明缺少右括号,不匹配;

解决代码

建议在pycharm中打断点,以便于更好的理解


  1. #!/use/bin/env python 
  2.  
  3. # _*_ coding:utf-8 _*_ 
  4.  
  5. LEFT = {'(''[''{'}  # 左括号 
  6.  
  7. RIGHT = {')'']''}'}  # 右括号 
  8.  
  9. def match(expr): 
  10.  
  11.     ""
  12.  
  13.     :param expr:  传过来的字符串 
  14.  
  15.     :return:  返回是否是正确的 
  16.  
  17.     ""
  18.  
  19.     stack = []  # 创建一个栈 
  20.  
  21.     for brackets in expr:  # 迭代传过来的所有字符串 
  22.  
  23.         if brackets in LEFT:  # 如果当前字符在左括号内 
  24.  
  25.             stack.append(brackets)  # 把当前左括号入栈 
  26.  
  27.         elif brackets in RIGHT:  # 如果是右括号 
  28.  
  29.             if not stack or not 1 <= ord(brackets) - ord(stack[-1]) <= 2: 
  30.  
  31.                 # 如果当前栈为空,()] 
  32.  
  33.                 # 如果右括号减去左括号的值不是小于等于2大于等于1 
  34.  
  35.                 return False  # 返回False 
  36.  
  37.             stack.pop()  # 删除左括号 
  38.  
  39.     return not stack  # 如果栈内没有值则返回True,否则返回False 
  40.  
  41. result = match('[(){()}]'
  42.  
  43. print(result)  

迷宫问题

题目

用一个二维数组表示一个简单的迷宫,用0表示通路,用1表示阻断,老鼠在每个点上可以移动相邻的东南西北四个点,设计一个算法,模拟老鼠走迷宫,找到从入口到出口的一条路径。

如图所示

出去的正确线路如图中的红线所示

思路

  1. 用一个栈来记录老鼠从入口到出口的路径
  2. 走到某点后,将该点左边压栈,并把该点值置为1,表示走过了;
  3. 从临近的四个点中可到达的点中任意选取一个,走到该点;
  4. 如果在到达某点后临近的4个点都不走,说明已经走入死胡同,此时退栈,退回一步尝试其他点;
  5. 反复执行第二、三、四步骤直到找到出口;

解决代码


  1. #!/use/bin/env python 
  2.  
  3. # _*_ coding:utf-8 _*_ 
  4.  
  5. def initMaze(): 
  6.  
  7.     ""
  8.  
  9.     :return: 初始化迷宫 
  10.  
  11.     ""
  12.  
  13.     maze = [[0] * 7 for _ in range(5 + 2)]  # 用列表解析创建一个7*7的二维数组,为了确保迷宫四周都是墙 
  14.  
  15.     walls = [  # 记录了墙的位置 
  16.  
  17.         (1, 3), 
  18.  
  19.         (2, 1), (2, 5), 
  20.  
  21.         (3, 3), (3, 4), 
  22.  
  23.         (4, 2),  # (4, 3),  # 如果把(4, 3)点也设置为墙,那么整个迷宫是走不出去的,所以会返回一个空列表 
  24.  
  25.         (5, 4) 
  26.  
  27.     ] 
  28.  
  29.     for i in range(7):  # 把迷宫的四周设置成墙 
  30.  
  31.         maze[i][0] = maze[i][-1] = 1 
  32.  
  33.         maze[0][i] = maze[-1][i] = 1 
  34.  
  35.     for i, j in walls:  # 把所有墙的点设置为1 
  36.  
  37.         maze[i][j] = 1 
  38.  
  39.     return maze 
  40.  
  41. ""
  42.  
  43. [1, 1, 1, 1, 1, 1, 1] 
  44.  
  45. [1, 0, 0, 1, 0, 0, 1] 
  46.  
  47. [1, 1, 0, 0, 0, 1, 1] 
  48.  
  49. [1, 0, 0, 1, 1, 0, 1] 
  50.  
  51. [1, 0, 1, 0, 0, 0, 1] 
  52.  
  53. [1, 0, 0, 0, 1, 0, 1] 
  54.  
  55. [1, 1, 1, 1, 1, 1, 1] 
  56.  
  57. ""
  58.  
  59. def path(maze, start, end): 
  60.  
  61.     ""
  62.  
  63.     :param maze: 迷宫 
  64.  
  65.     :param start: 起始点 
  66.  
  67.     :param end: 结束点 
  68.  
  69.     :return: 行走的每个点 
  70.  
  71.     ""
  72.  
  73.     i, j = start  # 分解起始点的坐标 
  74.  
  75.     ei, ej = end  # 分解结束点的左边 
  76.  
  77.     stack = [(i, j)]  # 创建一个栈,并让老鼠站到起始点的位置 
  78.  
  79.     maze[i][j] = 1  # 走过的路置为1 
  80.  
  81.     while stack:  # 栈不为空的时候继续走,否则退出 
  82.  
  83.         i, j = stack[-1]  # 获取当前老鼠所站的位置点 
  84.  
  85.         if (i, j) == (ei, ej): break  # 如果老鼠找到了出口 
  86.  
  87.         for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]:  # 左右上下 
  88.  
  89.             if maze[i + di][j + dj] == 0:  # 如果当前点可走 
  90.  
  91.                 maze[i + di][j + dj] = 1  # 把当前点置为1 
  92.  
  93.                 stack.append((i + di, j + dj))  # 把当前的位置添加到栈里面 
  94.  
  95.                 break 
  96.  
  97.         else:  # 如果所有的点都不可走 
  98.  
  99.             stack.pop()  # 退回上一步 
  100.  
  101.     return stack  # 如果迷宫不能走则返回空栈 
  102.  
  103. Maze = initMaze()  # 初始化迷宫 
  104.  
  105. result = path(maze=Maze, start=(1, 1), end=(5, 5))  # 老鼠开始走迷宫 
  106.  
  107. print(result) 
  108.  
  109. # [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (4, 3), (4, 4), (4, 5), (5, 5)]  

后缀表达式求值

题目

计算一个表达式时,编译器通常使用后缀表达式,这种表达式不需要括号:  

编写程序实现后缀表达式求值函数。

思路

  1. 建立一个栈来存储待计算的操作数;
  2. 遍历字符串,遇到操作数则压入栈中,遇到操作符号则出栈操作数(n次),进行相应的计算,计算结果是新的操作数压回栈中,等待计算
  3. 按上述过程,遍历完整个表达式,栈中只剩下最终结果;

解决代码


  1. #!/use/bin/env python 
  2.  
  3. # _*_ coding:utf-8 _*_ 
  4.  
  5. operators = {  # 运算符操作表 
  6.  
  7.     '+': lambda op1, op2: op1 + op2, 
  8.  
  9.     '-': lambda op1, op2: op1 - op2, 
  10.  
  11.     '*': lambda op1, op2: op1 * op2, 
  12.  
  13.     '/': lambda op1, op2: op1 / op2, 
  14.  
  15.  
  16. def evalPostfix(e): 
  17.  
  18.     ""
  19.  
  20.     :param e: 后缀表达式 
  21.  
  22.     :return: 正常情况下栈内的第一个元素就是计算好之后的值 
  23.  
  24.     ""
  25.  
  26.     tokens = e.split()  # 把传过来的后缀表达式切分成列表 
  27.  
  28.     stack = [] 
  29.  
  30.     for token in tokens:  # 迭代列表中的元素 
  31.  
  32.         if token.isdigit():  # 如果当前元素是数字 
  33.  
  34.             stack.append(int(token))  # 就追加到栈里边 
  35.  
  36.         elif token in operators.keys():  # 如果当前元素是操作符 
  37.  
  38.             f = operators[token]  # 获取运算符操作表中对应的lambda表达式 
  39.  
  40.             op2 = stack.pop()  # 根据先进后出的原则,先让第二个元素出栈 
  41.  
  42.             op1 = stack.pop()  # 在让第一个元素出栈 
  43.  
  44.             stack.append(f(op1, op2))  # 把计算的结果在放入到栈内 
  45.  
  46.     return stack.pop()  # 返回栈内的第一个元素 
  47.  
  48. result = evalPostfix('2 3 4 * +'
  49.  
  50. print(result) 
  51.  
  52. # 14  

背包问题

题目

有一个背包能装10kg的物品,现在有6件物品分别为:

编写找出所有能将背包装满的解,如物品1+物品5。

解决代码


  1. #!/use/bin/env python 
  2.  
  3. # _*_ coding:utf-8 _*_ 
  4.  
  5. def knapsack(t, w): 
  6.  
  7.     ""
  8.  
  9.     :param t: 背包总容量 
  10.  
  11.     :param w: 物品重量列表 
  12.  
  13.     :return
  14.  
  15.     ""
  16.  
  17.     n = len(w)  # 可选的物品数量 
  18.  
  19.     stack = []  # 创建一个栈 
  20.  
  21.     k = 0  # 当前所选择的物品游标 
  22.  
  23.     while stack or k < n:  # 栈不为空或者k<n 
  24.  
  25.         while t > 0 and k < n:  # 还有剩余空间并且有物品可装 
  26.  
  27.             if t >= w[k]:  # 剩余空间大于等于当前物品重量 
  28.  
  29.                 stack.append(k)  # 把物品装备背包 
  30.  
  31.                 t -= w[k]  # 背包空间减少 
  32.  
  33.             k += 1  # 继续向后找 
  34.  
  35.         if t == 0:  # 找到了解 
  36.  
  37.             print(stack) 
  38.  
  39.         # 回退过程 
  40.  
  41.         k = stack.pop()  # 把最后一个物品拿出来 
  42.  
  43.         t += w[k]  # 背包总容量加上w[k] 
  44.  
  45.         k += 1  # 装入下一个物品 
  46.  
  47. knapsack(10, [1, 8, 4, 3, 5, 2]) 
  48.  
  49. ""
  50.  
  51. [0, 2, 3, 5] 
  52.  
  53. [0, 2, 4] 
  54.  
  55. [1, 5] 
  56.  
  57. [3, 4, 5] 
  58.  
  59. """  



作者:佚名

来源:51CTO

网友评论

登录后评论
0/500
评论
行者武松
+ 关注