^

Young Anything I do that may help others, I'll post it here.

Basic data structure - stack

26 Jul 2016

python实现stack结构

以前怎么能这么嫩…全文不改了···

2017.12.4

教程来自杀了这个男孩的译文
原文来自Problem Solving with Algorithms and Data Structures

本文对以上两者内容进行了整理，并对代码进行了复现注释。

目录

0 利用python实现 Stack 结构 

# 注意: pythonds非python3自带模块,需要另行pip安装
from pythonds.basic.stack import Stack


# 类my_Stack复现 pythonds.basic.stack 小轮子,insert(0)和pop(0)需要O(C)
# 栈stack的特点——first in last out(FILO)
# list的最右侧作为栈顶
class my_Stack(object):
	def __init__(self):
		self.items = []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def peek(self):
		return self.items[-1]

	def size(self):
		return len(self.items)

	def isEmpty(self):
		return self.items == []


# 若将列表的头（左侧）作为栈顶,insert(0)和pop(0)却需要O(n)
class my_Stack_mirror(object):
	def __init__(self):
		self.items = []

	def push(self, item):
		self.items.insert(0, item)

	def pop(self):
		return self.items.pop(0)

	def peek(self):
		return self.items[0]

	def size(self):
		return len(self.items)

	def isEmpty(self):
		return self.items == []

返回目录

1 利用stack实现语句中的 大中小括号 匹配检测

def parChecker(sampleString):
	# 用来检测括号匹配的函数
	def matches(open, close):
		opens = '{[('
		closes = '}])'
		return opens.index(open) == closes.index(close)

	s = Stack()
	balance = True
	index = 0
	while index < len(sampleString) and balance:
		symbol = sampleString[index]
		if symbol not in '{}[]()':
			index += 1
			continue
		if symbol in '[{(':
			s.push(symbol)
		else:
			if s.isEmpty():
				balance = False
				break
			else:
				if matches(s.peek(), symbol):
					s.pop()
				else:
					balance = False
					break
		index += 1
	if s.isEmpty() and balance:
		return True
	else:
		return False


# 测试:
print(parChecker('print{}]'))
print(parChecker('}'))
print(parChecker('[{})'))

返回目录

2 利用stack实现 数字进制转换

from pythonds.basic.stack import Stack


def baseConverter(sampleNumber, base):
	# digits是为了能使16进制这种二位的进制方便显示
	digits = '0123456789ABCDEF'
	rems = Stack()
	while sampleNumber > 0:
		rem = sampleNumber % base
		rems.push(rem)
		sampleNumber = sampleNumber // base

	newstring = ''
	while not rems.isEmpty():
		newstring = newstring + digits[rems.pop()]
	return newstring


# test:

print(baseConverter(345, 2))
print(baseConverter(345, 8))
print(baseConverter(345, 16))
print(baseConverter(345, 10))

返回目录

3 利用stack实现 中缀表达式转换为后缀表达式

from pythonds.basic.stack import Stack

# Infix: 中缀
# Prefix: 前缀
# Postfix: 后缀

from pythonds.basic.stack import Stack


def infix_2_Postfix(infixexpr):
	prec = {}
	prec["*"] = 3
	prec["/"] = 3
	prec["+"] = 2
	prec["-"] = 2
	prec["("] = 1
	opStack = Stack()
	postfixList = []
	infixexpr = infixexpr.replace(' ', '')
	tokenList = [x for x in infixexpr]
	print(tokenList)
	for token in tokenList:
		# 操作数直接放到list里面
		if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':
			postfixList.append(token)
		elif token == '(':
			opStack.push(token)
		elif token == ')':
			topToken = opStack.pop()
			# 遇到')'就把栈内的符号一个个压出,直到压出一个'('
			while topToken != '(':
				postfixList.append(topToken)
				topToken = opStack.pop()
		else:
			# 若	token是操作符,且优先级比栈顶的操作符优先级低,就把栈顶的操作符压出放入list
			while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
				postfixList.append(opStack.pop())
			# 压出高优先级的操作符后,把token压入栈中
			opStack.push(token)
	# 接着把栈中剩余的操作符一个个放到list中
	while not opStack.isEmpty():
		postfixList.append(opStack.pop())
	return "".join(postfixList)


print(infix_2_Postfix('A * B + C * D'))
print(infix_2_Postfix('( A + B ) * C - ( D - E ) * ( F + G )'))
print(infix_2_Postfix('A+B-C'))

返回目录

4 利用stack实现 后缀表达式数值计算

from pythonds.basic.stack import Stack
# 设计后缀表达式计算函数

# 我的方法
def Postfix_calculate(infixexpr):
	numStack = Stack()
	infixexpr = infixexpr.replace(' ', '')
	tokenList = [x for x in infixexpr]

	for token in tokenList:
		if token in '0123456789':
			numStack.push(int(token))
		elif token == '+':
			numStack.push(numStack.pop() + numStack.pop())
		elif token == '+':
			numStack.push(-numStack.pop() + numStack.pop())
		elif token == '*':
			numStack.push(numStack.pop() * numStack.pop())
		else:
			numStack.push(1 / (numStack.pop() / numStack.pop()))

	return numStack.peek()


print(Postfix_calculate('78+32+/'))

# 书上的方法
def postfixEval(postfixExpr):
	operandStack = Stack()
	tokenList = postfixExpr.split()

	for token in tokenList:
		if token in "0123456789":
			operandStack.push(int(token))
		else:
			operand2 = operandStack.pop()
			operand1 = operandStack.pop()
			result = doMath(token, operand1, operand2)
			operandStack.push(result)
	return operandStack.pop()


def doMath(op, op1, op2):
	if op == "*":
		return op1 * op2
	elif op == "/":
		return op1 / op2
	elif op == "+":
		return op1 + op2
	else:
		return op1 - op2


print(postfixEval('7 8 + 3 2 + /'))

返回目录

Related Posts