栈的实现与应用

一、栈的实现

• 方法一：就使用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 Stack

def is_balance(mystr):
	s = Stack()
	#默认是对称的
	balance = True
	for item in mystr:
		if item == '(':
			s.push(item)
		elif item == ')':
			if s.isEmpty():
				#右括号多于左括号的情况
				balance = False
			s.pop()
	if not s.isEmpty():
		#左括号多于右括号的情况
		balance = False
	return balance

if __name__ == '__main__':
	print(is_balance('((()))'))
	print(is_balance('(()'))

2.2广义的平衡问题

#经典使用stack的场景：平衡括号问题
from stack import Stack

def is_balance(mystr):
	s = Stack()
	#默认是对称的
	balance = True

	for item in mystr:
		if item in sym_dict.keys():
			s.push(item)
		elif item in sym_dict.values():
			if s.isEmpty():
				#右括号多于左括号的情况
				balance = False
			elif sym_dict[s.peek()] == item:
				s.pop()
				
	if not s.isEmpty():
		#左括号多于右括号的情况
		balance = False
	return balance

if __name__ == '__main__':
	sym_dict = {
		'(': ')',
		'{': '}',
		'[': ']',
	} 
	print(is_balance('{{([][])}()}'))
	print(is_balance('[{()]'))

2.3 任意进制转换问题

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

from stack import Stack
from functools import reduce

def dec_to_any(num, base=2):
	s = Stack()
	symbol_bank = '0123456789ABCDE'
	#取余数，压入stack
	while num > 0:
		item = num % base
		s.push(item)
		#除法取整必须使用 //
		num = num // base

	#pop并拼凑出字符串
	result = ''
	for i in range(s.size()):
		result += symbol_bank[s.pop()]
	return result

def any_to_dec(num, base=2):
	s = Stack()
	symbol_bank = '0123456789ABCDE'
	result = 0
	i = 0
	for item in str(num):
		s.push(item)
	for i in range(s.size()):
		item = s.pop()
		result += symbol_bank.index(item) * base ** i
	return result

def 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 Timer

def 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 Stack

def 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('(')
						break
					out_list.append(top)
				#别忘了先把当前item push进去
				opstack.push(item)
		#当遇到')'，将opstack中元素pop并添加到out_list,知道遇到‘（’,左括号也要pop
		elif item == ')':
			while not opstack.isEmpty():
				top = opstack.pop()
				if top == '(':
					break
				out_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 Stack

def _do_math(stack, operator):
	#先pop出的数字为第二个操作数！！！一定要注意顺序
	operand2 = int(stack.pop())
	operand1 = int(stack.pop())
	if operator == '+':
		return operand1 + operand2
	if operator == '-':
		return operand1 - operand2
	if operator == '*':
		return operand1 * operand2
	if operator == '/':
		return operand1 / operand2

def 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