1. 棧
棧(Stack)是限制插入和刪除操作只能在一個位置進行的表，該位置是表的末端，稱為棧的頂(top)。堆疊的基本操作有PUSH(入棧)和POP(出棧)。堆疊又稱為LIFO(後入先出)表。
1.1 堆疊的實作
class Stack(object):
def __init__(self):
self.stack=[]
def isEmpty(self):
return self.stack==[]
def push(self,item):
self.stack.append(item)
def pop(self):
if self.isEmpty():
raise IndexError,'pop from empty stack'
return self.stack.pop()
def peek(self):
return self.stack[-1]
def size(self):
return len(self.stack)1.2 堆疊應用
1.2.1 檢查程式中成對的符號
程式的語法錯誤經常是由缺少一個符號造成的。可用堆疊來檢查符號是否成對。做一個空棧，如果字元是開放符號('({[')則將其push棧中。如果符號是個閉合符號(')]}'),則當棧空時報錯，對應'()}'的錯誤。否則，將堆疊pop，如果彈出的符號不是對應的開放符號，則報錯，對應'(}'的錯誤。文件末尾，如果棧為空，則報錯，對應'({}'的錯誤。
def match(i,j):
opens='([{'
closes=')]}'
return opens.index(i)==closes.index(j)
def syntaxChecker(string):
stack=Stack()
balanced=True
for i in string:
if i in '([{':
stack.push(i)
elif i in ')]}':
if stack.isEmpty():
balanced=False
break
else:
j=stack.pop()
if not match(j,i):
balanced=False
break
if not stack.isEmpty():
balanced=False
return balanced1.2.2 進制轉換
十進制轉換二進制：把十進制轉成二進制一直分解至商數為0。 Solving with Algorithms and Data Structures》的圖片：
碼：
def decimal_to_bin(dec):
stack=Stack()
cur=dec
while cur>0:
a=cur%2
cur=cur/2
stack.push(a)
binstr=''
while not stack.isEmpty():
binstr+=str(stack.pop())
return binstr
1.2.3 後綴記法
中綴到後綴到的轉換：當讀到一個操作數的時候，放到輸出。讀到運算元(+,-,*,/)時，如果堆疊為空，則壓入堆疊中，否則彈出堆疊元素放到輸出中直到發現優先權較低的元素為止。讀到'(',壓入棧中，讀到')',彈出棧元素並發到輸出中直到發現'('為止。在末尾，將棧元素彈出直到該棧變成空棧。
def infixtoPostfix(infix):
a={}
a['*']=3
a['/']=3
a['+']=2
a['-']=2
a['(']=1
stack=Stack()
post=''
for i in infix:
if i not in a and i!=')':
post+=i
elif i=='(':
stack.push(i)
elif i==')':
top=stack.pop()
while top!='(':
post+=top
top=stack.pop()
else:
while not stack.isEmpty() and a[i]<=a[stack.peek()]:
post+=stack.pop()
stack.push(i)
while not stack.isEmpty():
post+=stack.pop()
return post
def postfixExp(postfix):
stack=Stack()
postlist=postfix.split()
for i in postlist:
if i not in '+-*/':
stack.push(i)
else:
a=stack.pop()
b=stack.pop()
result=math(i,b,a)
stack.push(result)
return stack.pop()
def math(x,y,z):
if x=='+':
return float(y)+float(z)
if x=='-':
return float(y)-float(z)
if x=='*':
return float(y)*float(z)
if x=='/':
return float(y)/float(z)2 隊列
