Python栈算法的实现与简单应用示例

作者:做梦的人- 时间:2023-11-16 23:18:30 

本文实例讲述了Python栈算法的实现与简单应用。分享给大家供大家参考,具体如下:

原理:

栈作为一种数据结构,是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)

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

标签:Python,栈算法
0
投稿

猜你喜欢

  • Go语言中 Channel 详解

    2024-01-30 04:39:48
  • Mysql中文乱码以及导出为sql语句和Excel问题解决方法[图文]

    2024-01-17 10:23:24
  • Python实现Appium端口检测与释放的实现

    2023-03-08 08:34:23
  • 关于Mysql-connector-java驱动版本问题总结

    2024-01-19 02:07:58
  • 在ASP中使用SQL语句之7:ORDER BY

    2007-08-11 12:51:00
  • ubuntu下简单配置mysql数据库

    2009-07-31 09:17:00
  • 网马解密大讲堂——网马解密初级篇

    2009-09-16 14:45:00
  • cv2.getStructuringElement()函数及开、闭、腐蚀、膨胀原理讲解

    2023-08-24 23:07:23
  • QML使用Python的函数过程解析

    2021-12-10 19:20:31
  • 解决python -m pip install --upgrade pip 升级不成功问题

    2022-12-15 00:21:55
  • 搭建 Selenium+Python开发环境详细步骤

    2022-10-12 17:34:02
  • JavaScript的一些小技巧分享

    2024-04-23 09:29:01
  • 详解Windows下安装Nodejs步骤

    2024-05-03 15:56:34
  • 十分钟利用Python制作属于你自己的个性logo

    2021-08-25 05:12:41
  • mysql的case when字段为空,null的问题

    2024-01-13 14:40:59
  • ASP获取当前页面URL地址(带参数)的方法

    2010-01-14 19:40:00
  • php购物车实现方法

    2023-11-16 22:54:51
  • Ubuntu下使用python读取doc和docx文档的内容方法

    2021-04-09 03:42:30
  • asp如何用JMail POP3接收电子邮件?

    2010-06-13 13:09:00
  • Python3.10耙梳加密算法Encryption种类及开发场景

    2021-07-19 00:46:55
  • asp之家 网络编程 m.aspxhome.com