栈的实现与应用

一、栈的实现

• 方法一：就使用list即可

先进后出

• 方法二：定义Stack,抽象出栈

class Stack:#栈的python实现def __init__(self):self.items = []def push(self, item):#append操作O(1)self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[-1]def isEmpty(self):return self.items == []def size(self):return len(self.items)

二、栈的应用

2.1平衡括号问题

#经典使用stack的场景：平衡括号问题 from stack import Stackdef is_balance(mystr):s = Stack()#默认是对称的balance = Truefor item in mystr:if item == '(':s.push(item)elif item == ')':if s.isEmpty():#右括号多于左括号的情况balance = Falses.pop()if not s.isEmpty():#左括号多于右括号的情况balance = Falsereturn balanceif __name__ == '__main__':print(is_balance('((()))'))print(is_balance('(()'))

2.2广义的平衡问题

#经典使用stack的场景：平衡括号问题 from stack import Stackdef is_balance(mystr):s = Stack()#默认是对称的balance = Truefor item in mystr:if item in sym_dict.keys():s.push(item)elif item in sym_dict.values():if s.isEmpty():#右括号多于左括号的情况balance = Falseelif sym_dict[s.peek()] == item:s.pop()if not s.isEmpty():#左括号多于右括号的情况balance = Falsereturn balanceif __name__ == '__main__':sym_dict = {'(': ')','{': '}','[': ']',} print(is_balance('{{([][])}()}'))print(is_balance('[{()]'))

2.3 任意进制转换问题

十进制转换到其他进制时，存在取余最后求反的过程，这个求反过程如果利用stack这种数据结构，可以节省reverse(list)的O(n)操作！

from stack import Stack from functools import reducedef dec_to_any(num, base=2):s = Stack()symbol_bank = '0123456789ABCDE'#取余数，压入stackwhile num > 0:item = num % bases.push(item)#除法取整必须使用 //num = num // base#pop并拼凑出字符串result = ''for i in range(s.size()):result += symbol_bank[s.pop()]return resultdef any_to_dec(num, base=2):s = Stack()symbol_bank = '0123456789ABCDE'result = 0i = 0for item in str(num):s.push(item)for i in range(s.size()):item = s.pop()result += symbol_bank.index(item) * base ** ireturn resultdef conversion(num, from_base, to_base):temp = any_to_dec(num, from_base)return dec_to_any(temp, to_base)if __name__ == '__main__':print(dec_to_any(25,2))print(dec_to_any(25,16))print(any_to_dec(11001,2))print(any_to_dec(19,16))print(conversion(11001,2,8))

• 注意：

使用reverse来翻转list比使用stack快10000倍，单纯的翻转操作肯定选reverse，但是stack在入栈以及出栈的时候可以进行一系列的操作，对于某一类问题非常合适！！

from stack import Stack import timeit from timeit import Timerdef reverse_list1(mylist):reversed(mylist)def reverse_list2(mylist):s = Stack()result = []for i in mylist:s.push(i)for i in range(s.size()):mylist[i] = s.pop()if __name__ == '__main__':a = list(range(10000))t1 = Timer('reverse_list1(a)', 'from __main__ import reverse_list1,a')print(t1.timeit(number=100))t2 = Timer('reverse_list2(a)', 'from __main__ import reverse_list2,a')print(t2.timeit(number=100))

2.4中缀表达式转换

2.4.1 转为后缀表达式

AB+CD -> ABCD+

特征：

• ABCD这些操作数的相对位置不变，直接用一个list逐个存储即可
• 操作符’+’优先级小于C与D之间的*,故结果中这两个操作符位置肯定要颠倒，想到用stack的特性
• 括号也要压入stack,括号内的操作符相当于一个子过程，只有当‘）‘出现，才可以pop从左括号到右括号的所有元素，继续进行程序

解题思路：

以 "A * B + C * D"为例

#stack综合运用 #启发：stack不仅在入栈、出栈过程中可以做文章，比如筛选等操作， #同时，不一定要全部元素入栈后全部再出栈，可以入一部分、出一部分、再入 from stack import Stackdef postpix(exp):opstack = Stack()out_list = []exp = exp.split(' ')for item in exp:if item in operator_bank:if opstack.isEmpty():opstack.push(item)elif operator_bank[opstack.peek()] <= operator_bank[item]:opstack.push(item)else:#当opstack非空，且peek优先值大于当前item,则将opstack'('之后所有操作符pop并添加到out_list,不包括左括号while not opstack.isEmpty():top = opstack.pop()if top == '(':opstack.push('(')breakout_list.append(top)#别忘了先把当前item push进去opstack.push(item)#当遇到')'，将opstack中元素pop并添加到out_list,知道遇到‘（’,左括号也要popelif item == ')':while not opstack.isEmpty():top = opstack.pop()if top == '(':breakout_list.append(top)#当字符为操作数else:out_list.append(item)while(not opstack.isEmpty()):top = opstack.pop()out_list.append(top)return ''.join(out_list)if __name__ == '__main__':operator_bank = {'(': 2,'*': 1,'/': 1,'+': 0,'-': 0,}operand_bank = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'# print(postpix("A*B+C*D"))print(postpix("( A + B ) * C - ( D - E ) * ( F + G )"))

2.4.2 后缀表达式求值

思路：

以 "7 8 + 3 2 + /"为例

实现：

from stack import Stackdef _do_math(stack, operator):#先pop出的数字为第二个操作数！！！一定要注意顺序operand2 = int(stack.pop())operand1 = int(stack.pop())if operator == '+':return operand1 + operand2if operator == '-':return operand1 - operand2if operator == '*':return operand1 * operand2if operator == '/':return operand1 / operand2def evaluate_postfix(exp):"""求后缀算数表达式的值"""operand_stack = Stack()exp_list = exp.split(' ')for item in exp_list:if item in operand_bank:operand_stack.push(item)else:temp = _do_math(operand_stack,item)operand_stack.push(temp)return operand_stack.pop()if __name__ == '__main__':operand_bank = '123456789'print(evaluate_postfix('7 8 + 3 2 + /'))

三、参考

http://interactivepython.org/runestone/static/pythonds/BasicDS/toctree.html

总结

以上是生活随笔为你收集整理的栈的实现与应用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。