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 balanced
1.2.2 进制转换
十进制转换二进制：把十进制转成二进制一直分解至商数为0。从最底左边数字开始读，之后读右边的数字，从下读到上。
来自《problem 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 后缀记法
后缀记法(postfix)，使用一个栈，见到一个数时入栈，遇到一个运算符时就作用于从栈弹出的两个元素，将结果弹入栈中。
(7+8)/(3+2)可以写作7 8 + 3 2 + /
来自《problem solving with algorithms and data structures》的图片：
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]