Python栈算法的实现与简单应用示例
作者:做梦的人- 发布时间:2023-11-16 23:18:30
本文实例讲述了Python栈算法的实现与简单应用。分享给大家供大家参考,具体如下:
原理:
栈作为一种数据结构,是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)
桟的应用场景非常多:1、内存管理中使用的堆栈;2、基于桟实现的二叉树的遍历;3、在语言处理中,符号的平衡问题,在语言中,往往很多符号是成对出现的,比如<>,{},[],()等,如何判断符号是否漏了,一种实现方式就是:假设在读入一串字符串以后,如果遇到对称符号的左边部分,则将其压入栈中,当遇到对称符号的右边部分,则弹出栈中的一个对象,如果所有的符号都是平衡的,栈中此时应该就是为空,通过判断栈中是否为空,说明字符串是否是符号平衡的。
在桟的设计中,我们需要定义一个实例属性top。三个实例方法:获取栈顶元素peek();出桟pop();入栈push()
实例属性:self.top,要先找到一个标点,或者是能够定位的一个点,作为一个基准
实例方法:
1、入栈
把node.next=top 把入栈的节点,给一个top
top=node #节点进来后,就是这个节点返回给
返回top的value
2、出栈
1)是否是空栈,是的话,返回None
2)否则,返回top.value,并且top指向下一个节点
发现队列或栈其实都需要找到一个节点,需要找到你现在的位置,
#给一个点,我们能够根据这个点知道一些内容
class Node(object):
def __init__(self): #定位的点的值和一个指向
self.val=val #指向元素的值,原队列第二元素
self.next=None #指向的指针
class stack(object):
def __init__(self):
self.top=None #初始化最开始的位置
def peek(self): #获取栈顶的元素
if self.top!=None: #如果栈顶不为空
return self.top.val #返回栈顶元素的值
else:
return None
def push(self,n):#添加到栈中
n=Node(n) #实例化节点
n.next=self.top #顶端元素传值给一个指针
self.top=n #
return n.val
def pop(self): #退出栈
if self.top == None:
return None
else:
tmp=self.top.val
self.top=self.top.next #下移一位,进行
return tmp
if __name__=="__main__":
s=stack()
s.push(1)
s.push(2)
s.push(3)
print s.pop()
print s.pop()
print s.pop()
打印的效果
3
2
1
应用:
数制转换:
1. 硬编码实现
#--coding: utf - 8--""
"
N = input("Please input a number::")
while (N):
print "** @ **"
N -= 1 ""
"
N = input("输入十进制数字(换算为八进制)::")
stack = []
string8 = ""
while (N):
#求余
stack.append(N % 8)# 求商
N = N //8
while (len(stack) > 0):
string8 += str(stack.pop())
print "转换为八进制:" + string8
2. 构建stack类,来实现
Stack1.py
#--coding: utf - 8--
class Stack(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def GetTop(self):
return
self.items[len(self.items) - 1]
moshi.py
#--coding: utf - 8--
import stack1
shiyan = stack1.Stack()
stringu = ""
temp = input("请输入一个十进制数字::")
while (temp):
shiyan.push(temp % 8)
temp = temp / 8
while (not shiyan.isEmpty()):
stringu += str(shiyan.pop())
print "八进制为::" + stringu
括号匹配
硬编码实现
#--coding:utf-8--
print " ****括号匹配**** "
print """
输入原则: 每当你输入一个括号, 你需要再输入一个‘,'
进行区分, 例如:(, [, ], (, ), )
输入的可识别括号有(), [], {}
"""
strpp = raw_input("请输入一段括号表达式:")
basestr = strpp.split(',')
pstack = []
suoyin = {'(': ')','[': ']','{': '}'}
for e in basestr:
if (e == '(' or e == '[' or e == '}'):
pstack.append(e)
else :
if len(pstack) == 0:
print "右括号多余"
break
else :
if e == suoyin[pstack[len(pstack) - 1]]:
pstack.pop()
else :
print "不匹配"
print "右括号多余"
break
if len(pstack) == 0:
print "匹配正确"
else :
print "左括号多余"
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/chongyou/p/7099692.html
猜你喜欢
- 反射反射即想到4个内置函数分别为:getattr、hasattr、setattr、delattr 获取成员、检查成员、设置成员、
- 首先需要安装Win32-ODBC模块,具体的步骤如下:1:从TOOLS栏目中下载Win32-ODBC.zip,下载完后用winzip解开到一
- 基本命令显示版本信息pip -V安装指定包pip install <packages>pip install -i 'h
- 在 Python 中,if 语句用于根据条件执行不同的代码块。它的基本格式如下:if condition: # 如
- 本文实例讲述了Python高级编程之继承问题。分享给大家供大家参考,具体如下:多继承问题1.单独调用父类: 一个子类同时继承自多个父类,又称
- 对于程序开发新手来说,一个最常见的困惑是测试的主题。他们隐约觉得“单元测试”是很好的,而且他们也应该做单元测试。但他们却不懂这个词的真正含义
- 前言登录跳转:不同的用户在登录成功之后跳转到不同的网页当中例如:网站管理员登录成功后跳转到网站后台,vip用户登录成功后跳转到vip页面准备
- 简介如何简单的使用python来实现将一部视频转换为字符画视频的效果。 其实,大家都知道视频就是一帧一帧的图片构成的。  
- 本文实例讲述了Python去除列表中重复元素的方法。分享给大家供大家参考。具体如下:比较容易记忆的是用内置的setl1 = ['b&
- 在Dreamweaver4中,你可以存储你自己设定的图片、链接、flash影片、颜色表、模板等等,组成这个站点的资产,这就是Assets面板
- 整本书围绕着一个叫做“CSS禅意花园”的网站展开,其实N久之前我在一份外国的关于CSS的在线教程上看到了这个网站的链接,可惜进去之后发现内容
- <% '测试读取MySql数据库的内容strconnection="driver={mysql odbc 3.51 dri
- 相信为数不少的系统管理员每天都在做着同一样的工作——对数据进行备份。一旦哪一天疏忽了,而这一天系统又恰恰发生了故障,需要进行数据恢复,那么此
- SQL Server 2000使得以XML导出数据变得更加简单,但在SQL Server 2000中导入XML数据并对其进行处理则有些麻烦。
- 如何提取JSON数据指定内容假设我们要获取'pic_str'里的数据JSON数据{'err_no': 0,
- 程序运行,产生如下结果,然后进程终止,导致这一结果的原因很有可能是内存 * 。当两个较大的 (e.g., 10000*10000 维)ndar
- django中的超链接,在template中可以用{% url 'app_name:url_name' param%}其中a
- Log包Go语言提供的默认日志包:https://golang.org/pkg/log/基本用法log包定义了Logger类型,该类型提供了
- 1.介绍 在计算机科学中,数据可以用很多不同的方式表示,自然而然地,每一种方式在某些领域都有其优点和
- 基于python+OpenCV的车牌号码识别,供大家参考,具体内容如下车牌识别行业已具备一定的市场规模,在电子警察、公路卡口、停车场、商业管