您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > Python

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

时间:2021-04-06 12:04:43  来源:今日头条  作者: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=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

2、进制转换

十进制转换二进制:把十进制转成二进制一直分解至商数为0。从最底左边数字开始读,之后读右边的数字,从下读到上。

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

进制转化

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

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

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

后缀记法

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)


Tags:python基础   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
Python 有 while 语句和 for 语句作为循环处理。虽然 for 语句具有一定数量的进程,但是 while 语句是『直到满足条件』类型的循环进程。 对于无限迭代 while,循环执行的次数没...【详细内容】
2022-06-14  Tags: python基础  点击:(60)  评论:(0)  加入收藏
Python基础知识建议有程序语言基础的童鞋阅读,零基础阅读可能会有点费解 文章目录Python基础知识注释方法数据类型输入和输出输入输出算数运算符常用运算函数比较运算符逻辑...【详细内容】
2022-01-10  Tags: python基础  点击:(90)  评论:(0)  加入收藏
random模块是Python中一个用于生成随机数的模块,其中包含了生成伪代随机数的函数,有助于编写模拟程序或者生成随机输出的程序。需要注意的是这些数虽然看起来好像是完全随机的...【详细内容】
2021-08-16  Tags: python基础  点击:(243)  评论:(0)  加入收藏
Python简单易学,简单到没有学过任何编程语言的人浏览一下资料,浏览一下示例,就可以编写出可用的程序;这是一种解释式编程语言,它可以直接编写,无需编译,在发现错误后立即进行修改,节...【详细内容】
2021-06-25  Tags: python基础  点击:(180)  评论:(0)  加入收藏
一、栈栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈...【详细内容】
2021-04-06  Tags: python基础  点击:(324)  评论:(0)  加入收藏
Python这么强,能不能让它解决一下难倒无数人的奇葩数学题呢?今天我们就用Python求解几个实际的数学题来了解一下Python的一些基本的算法。如果你刚好入门Python,懂一些Python的...【详细内容】
2020-08-03  Tags: python基础  点击:(84)  评论:(0)  加入收藏
想一起学习编程Python的同学,趁我粉丝少,可以留言、私信领编程资料~Python基础入门既然学习 Python,那么至少得了解下这门编程语言,知道 Python 代码执行过程吧。Python 的历史...【详细内容】
2020-07-30  Tags: python基础  点击:(76)  评论:(0)  加入收藏
大家好,这里是弘创共享时刻。 本视频是面向编程零基础学员的Python入门教程,内容涵盖了Python的基础知识和初步应用。以较轻快的风格,向零基础学习者介绍了一门时下比较流行的...【详细内容】
2020-07-08  Tags: python基础  点击:(80)  评论:(0)  加入收藏
前言学一门语言贵在坚持用它,不用就淡忘了,而记录下一篇文章也有助于日后快速回忆。全文分为两大部分,分别是Python基础语法和面向对象。第一部分 Python基础语法1. 认识Pyth...【详细内容】
2020-05-08  Tags: python基础  点击:(84)  评论:(0)  加入收藏
1.1 变量和赋值语句#使用Python变量前必须给它赋值,因为其无默认值x=31.2 Python神奇之处1#可同时给多个变量赋值x,y,z=1,2,3a=b=123#简单的多变量间值交换a,b,c,d=&#39;a&#3...【详细内容】
2019-11-25  Tags: python基础  点击:(138)  评论:(0)  加入收藏
▌简易百科推荐
近几年 Web3 被炒得火热,但是大部分人可能还不清楚什么是 Web3,今天就让w3cschool编程狮小师妹带你了解下 Web3 是什么?与我们熟知的 Web1 和 Web2 又有什么区别呢?web3.0什么是...【详细内容】
2022-07-15  编程狮W3Cschool    Tags:Web3.0   点击:(2)  评论:(0)  加入收藏
1、让我们一起来看下吧,直接上图。 第一眼看到是不是觉得很高逼格,暗黑画风,这很大佬。其实它就是------AidLearning。一个运行在安卓平台的linux系统,而且还包含了许多非常强大...【详细内容】
2022-07-15  IT智能化专栏    Tags:AidLearning   点击:(2)  评论:(0)  加入收藏
真正的大师,永远都怀着一颗学徒的心! 一、项目简介 今天说的这个软件是一款基于Python+vue的自动化运维、完全开源的云管理平台。二、实现功能 基于RBAC权限系统 录像回放 ...【详细内容】
2022-07-14  菜鸟程序猿    Tags:Python   点击:(3)  评论:(0)  加入收藏
前言今天笔者想和大家来聊聊python接口自动化的MySQL数据连接,废话不多说咱们直接进入主题吧。 一、什么是 PyMySQL?PyMySQL是在Python3.x版本中用于连接MySQL服务器的一个库,P...【详细内容】
2022-07-11  测试架构师百里    Tags:python   点击:(19)  评论:(0)  加入收藏
aiohttp什么是 aiohttp?一个异步的 HTTP 客户端\服务端框架,基于 asyncio 的异步模块。可用于实现异步爬虫,更快于 requests 的同步爬虫。安装pip install aiohttpaiohttp 和 r...【详细内容】
2022-07-11  VT漫步    Tags:aiohttp   点击:(15)  评论:(0)  加入收藏
今天我们学习下 Queue 的进阶用法。生产者消费者模型在并发编程中,比如爬虫,有的线程负责爬取数据,有的线程负责对爬取到的数据做处理(清洗、分类和入库)。假如他们是直接交互的,...【详细内容】
2022-07-06  VT漫步    Tags:Python Queue   点击:(34)  评论:(0)  加入收藏
继承:是面向对象编程最重要的特性之一,例如,我们每个人都从祖辈和父母那里继承了一些体貌特征,但每个人却又不同于父母,有自己独有的一些特性。在面向对象中被继承的类是父类或基...【详细内容】
2022-07-06  至尊小狸子    Tags:python   点击:(25)  评论:(0)  加入收藏
点击上方头像关注我,每周上午 09:00准时推送,每月不定期赠送技术书籍。本文1553字,阅读约需4分钟 Hi,大家好,我是CoCo。在上一篇Python自动化测试系列文章:Python自动化测试之P...【详细内容】
2022-07-05  CoCo的软件测试小栈    Tags:Python   点击:(27)  评论:(0)  加入收藏
第一种方式:res = requests.get(url, params=data, headers = headers)第二种方式:res = requests.get(url, data=data, headers = headers)注意:1.url格式入参只支持第一种方...【详细内容】
2022-07-05  独钓寒江雪之IT    Tags:Python request   点击:(19)  评论:(0)  加入收藏
什么是python类的多态python的多态,可以为不同的类实例,或者说不同的数据处理方式,提供统一的接口。用比喻的方式理解python类的多态比如,同一个苹果(统一的接口)在孩子的眼里(类实...【详细内容】
2022-07-04  写小说的程序员    Tags:python类   点击:(28)  评论:(0)  加入收藏
站内最新
站内热门
站内头条