python基础——数据结构栈的详解 _python基础

一、栈栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈(Stack)是限制插入和删除操作只能在一个位置进行的表，该位置是表的末端，称为栈的顶(top) 。栈的基本操作有PUSH(入栈)和POP(出栈) 。栈又被称为LIFO(后入先出)表。
二、栈的实现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、检查程序中成对的符号
程序的语法错误经常是由缺少一个符号造成的。可用栈来检查符号是否成对。做一个空栈，如果字符是开放符号('({[')则将其push栈中。如果符号是个闭合符号(')]}'),则当栈空时报错，对应'()}'的错误。否则，将栈pop，如果弹出的符号不是对应的开放符号，则报错，对应'(}'的错误。文件末尾，如果栈为空，则报错，对应'({}'的错误。
def match(i,j):opens='([{'closes=')]}'return opens.index(i)==closes.index(j)def syntaxChecker(string):stack=Stack()balanced=Truefor i in string:if i in '([{':stack.push(i)elif i in ')]}':if stack.isEmpty():balanced=Falsebreakelse:j=stack.pop()if not match(j,i):balanced=Falsebreakif not stack.isEmpty():balanced=Falsereturn balanced2、进制转换
十进制转换二进制：把十进制转成二进制一直分解至商数为0 。从最底左边数字开始读，之后读右边的数字，从下读到上。

文章插图
进制转化

def decimal_to_bin(dec):stack=Stack()cur=decwhile cur>0:a=cur%2cur=cur/2stack.push(a)binstr=''while not stack.isEmpty():binstr+=str(stack.pop())return binstr

3、后缀记法
后缀记法(postfix)，使用一个栈，见到一个数时入栈，遇到一个运算符时就作用于从栈弹出的两个元素，将结果弹入栈中。
(7+8)/(3+2)可以写作7 8 + 3 2 + /

文章插图
后缀记法

def infixtoPostfix(infix):a={}a['*']=3a['/']=3a['+']=2a['-']=2a['(']=1stack=Stack()post=''for i in infix:if i not in a and i!=')':post+=ielif i=='(':stack.push(i)elif i==')':top=stack.pop()while top!='(':post+=toptop=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 postdef 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)

【python基础——数据结构栈的详解】