栈的数据结构模型：
栈是一种有次序的数据项集合， 在栈中， 数据项的加入和移除都仅发生在同一端，这一端叫栈顶，另一端叫栈底。
距离栈底越近的数据项， 留在栈中的时间就越长，而最新加入栈的数据项会被最先移除，也即“后进先出LIFO”。
使用Python实现ADT Stack:
选用最常用的数据集list来实现，选用list的末端（index=-1）作为栈顶，就可以通过对list的append和pop来实现栈的push和pop，会比较简单。
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items(len(self.items)-1)
def size(self):
return len(self.items)
栈的应用：
- 简单括号匹配
import Stack
'''
简单括号匹配
输入字符串只包含 ( ) [ ] { }
输出True False
'''
def parChecker(symbolString):
s = Stack.Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "([{":
s.push(symbol)
else:
if s.is_empty():
balanced = False
else:
top = s.pop()
if not match(top, symbol):
balanced = False
index = index + 1
if balanced and s.is_empty():
return True
else:
return False
def match(left, right):
opens = "([{"
closes = ")]}"
return opens.index(left) == closes.index(right)
print(parChecker('([])'))
print(parChecker('()[]{}'))
print(parChecker('(([{]}))'))
- 进制转换
from Stack import Stack
'''
进制转换
输入10进制数字以及需要转换到的进制位数
输出转换后的对应进制的字符串
'''
def baseConvert(decNumber, base):
digit = "0123456789ABCDEF"
tranStack = Stack()
while decNumber > 0:
rem = decNumber % base
tranStack.push(rem)
decNumber = decNumber // base
newString= ""
while not tranStack.is_empty():
newString = newString + digit[tranStack.pop()]
return newString
print(baseConvert(13, 8))
print(baseConvert(13, 16))
-
表达式转换（中缀转后缀）
思路：
- 将中缀表达式转换为单词（token）列表
- 从左到右逐个字符扫描中缀表达式的过程中，采用一个opstack栈来暂存未处理的操作符。
- 如果单词是操作数，则直接添加到后缀表达式列表的末尾。
- 如果单词是"("，则压入opstack栈顶。
- 如果单词是")"，则反复弹出opstack栈顶操作符，加入到输出列表末尾，直到碰到左括号。
- 如果单词是操作符"*/+-"，则压入opstack的栈顶。但在压入之前，要比较其与栈顶操作符的优先级，如果栈顶的高于或者等于它，就要反复弹出栈顶操作符，加入到输出列表末尾。
- 中缀表达式单词列表扫描结束后，把opstack栈中的所有剩余操作符依次弹出，添加到输出列表末尾。
- 把输出列表再用join方法合并成后缀表达式字符串，算法结束。
from Stack import Stack
def infixToPostfix(infixExp):
opStack = Stack()
expList = []
indexToken = {}
indexToken["("] = 0
indexToken[")"] = 0
indexToken["+"]= 1
indexToken["-"] = 1
indexToken["*"] = 2
indexToken["/"] = 2
for token in infixExp:
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "123456789":
expList.append(token)
elif token is "(":
opStack.push(token)
elif token is ")":
topToken = opStack.pop()
while topToken is not "(":
expList.append(topToken)
topToken = opStack.pop()
elif token in "+-*/":
while (not opStack.is_empty()) and (indexToken[opStack.peek()] >= indexToken[token]):
expList.append(opStack.pop())
opStack.push(token)
while not opStack.is_empty():
expList.append(opStack.pop())
return "".join(expList)
print(infixToPostfix("3+2*5"))
print(infixToPostfix("(3+2)*5"))
print(infixToPostfix("(3+2*5)*5"))
-
后缀表达式求值
思路：
- 创建空栈opStack暂存操作数。
- 从左到右逐个字符扫描后缀表达式的过程中，
- 如果单词是操作数，则先转换为int，然后压入opStack中。
- 如果单词是"+-*/"，则取出opstack栈顶的两个元素进行操作，先弹出右操作数后弹出左操作数，计算后的值压入栈中。
- 单词列表扫描完成，表达式的值在栈顶。
from Stack import Stack
def postFixCal(postFixStr):
opStack = Stack()
for token in postFixStr:
if token in "123456789":
opStack.push(int(token))
else:
rightOps = opStack.pop()
leftOps = opStack.pop()
result = doMath(token,int(rightOps),int(leftOps))
opStack.push(result)
return opStack.pop()
def doMath(token,rightOps,leftOps):
if token is "+":
return rightOps+leftOps
elif token is "-":
return rightOps - leftOps
elif token is "*":
return rightOps * leftOps
elif token is "/":
return rightOps / leftOps
print(postFixCal("325*+"))
print(postFixCal("325*+5*"))
