iis服务器助手广告广告
返回顶部
首页 > 资讯 > 后端开发 > Python >Python数据结构与算法中的栈怎么实现
  • 225
分享到

Python数据结构与算法中的栈怎么实现

2023-06-29 10:06:42 225人浏览 薄情痞子

Python 官方文档:入门教程 => 点击学习

摘要

这篇文章主要介绍“python数据结构与算法中的栈怎么实现”,在日常操作中,相信很多人在Python数据结构与算法中的栈怎么实现问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Python数据结构与算法中的栈怎

这篇文章主要介绍“python数据结构与算法中的栈怎么实现”,在日常操作中,相信很多人在Python数据结构算法中的栈怎么实现问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Python数据结构与算法中的栈怎么实现”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

匹配括号

接下来,我们使用栈解决实际的计算机科学问题。

比如我们都写过这样所示的算术表达式, ( 5 + 6 ) ∗ ( 7 + 8 ) / ( 4 + 3 ) (5 + 6) * (7 + 8) / (4 + 3) (5+6)∗(7+8)/(4+3),其中的括号用来改变计算顺序,或提升运算优先级。

匹配括号是指每一个左括号都有与之对应的一个右括号,并且括号对有正确的嵌套关系

  • 正确的嵌套关系: ( ( ) ( ) ( ) ( ) ) (()()()()) (()()()())、 ( ( ( ( ) ) ) ) (((()))) (((())))、 ( ( ) ( ( ( ) ) ( ) ) ) (()((())())) (()((())()))

  • 错误的嵌套关系: ( ( ( ( ( ( ( ) ) ((((((()) ((((((())、 ( ) ) ) ())) ()))

我们的挑战就是编写一个算法,它从左到右读取一个括号串(不包括其他数字与运算符),然后判断其中的括号是否匹配

为了解决这个问题, 需要注意到一个重要现象。当从左到右处理括号时,最右边的无匹配左括号必须与接下来遇到的第一个右括号相匹配。并且,在第一个位置的左括号可能要等到处理至最后一个位置的右括号时才能完成匹配。而且右括号的出现顺序,与其相匹配的左括号的出现顺序相反。这一规律暗示着能够运用栈来解决括号匹配问题。

一旦认识到用来保存括号,算法编写起来就会十分容易。

由一个空栈开始,从左往右依次处理括号。如果遇到左括号,便通过栈的push操作将其加入栈中,以此表示稍后需要有一个与之匹配的右括号。

反之,如果遇到右括号,就调用栈的pop操作。只要栈中的所有左括号都能遇到与之匹配的右括号,那么整个括号串就是匹配的;如果栈中有任何一个左括号找不到与之匹配的右括号,则括号串就是不匹配的。在处理完匹配的括号串之后,栈应该是空的。

用简单的话说就是:扫描括号串,左括号入栈,遇见右括号,从栈顶取出来一个左括号配对儿,互相抵消,直到最后。如果括号匹配,那么栈最后就该是空的,并且括号串刚好扫描完毕。

代码实现如下:

class Stack:    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 parChecker(symbolString):    s = Stack()  # 构造栈    balanced = True  # 匹配标志 默认为True 表示匹配    index = 0  # 索引 用来取字符    # 当 索引小于字符串的长度 并且 匹配标志为True 时    while index < len(symbolString) and balanced:        # 取字符串当前位的字符        symbol = symbolString[index]        # 如果当前字符为 左括号 则入栈        if symbol == '(':            s.push(symbol)        # 如果当前字符 不是左括号(那当前就是右括号)        else:            # 并且栈是空的            if s.isEmpty():                # 匹配标志设置为 False 表示匹配失败(孤零零的右括号)                balanced = False            # 栈不是空的 抵消栈顶的左括号            else:                s.pop()        # 索引向后移动一位        index = index + 1    # 循环结束 如果匹配成功 并且 栈空了    if balanced and s.isEmpty():        return True    else:        return False

注意,balanced 的初始值是True,这是因为一开始没有任何理由假设其为False 。如果当前的符号是左括号,它就会被压入栈中(第27行)。注意第36行,仅通过pop()将一个元素从栈顶移除。由于移除的元素一定是之前遇到的左括号,因此并没有用到pop()的返回值。在第42~45行, 只要所有括号匹配并且栈为空,函数就会返回True ,否则返回False。

匹配符号

符号匹配是许多编程语言中的常见问题,括号匹配问题只是它的一个特例。我们已经会了匹配括号的方法,那么现在我们来试试匹配符号。

匹配符号是指正确地匹配和嵌套左右对应的符号

例如,在Python中,方括号“[”和“]”用于列表;花括号“{”和“}”用于字典;括号“(”和“)”用于元组和算术表达式。只要保证左右符号匹配,就可以混用这些符号。以下符号串是匹配的,其中不仅每一个左符号都有一个右符号与之对应,而且两个符号的类型也是一致的。

  • { { ( [ ] [ ] ) } ( ) }

  • [ [ { { ( ( ) ) } } ] ]

  • [ ] [ ] [ ] ( ) { }

以下符号则是不匹配的:

  • ( [ ) ]

  • ( ( ( ) ] ) )

  • [ { ( ) ]

要处理新类型的符号,我们扩展上面的括号匹配检测代码。

即每一个左符号都将被压入栈中,以待之后出现对应的右符号

唯一的区别在于,当出现右符号时,必须先检测其类型是否与栈顶的左符号类型相匹配。如果两个符号不匹配,那么整个符号串也就不匹配。同样,如果整个符号串处理完成并且栈是空的,那么就说明所有符号正确匹配。

代码实现如下:

class Stack:    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 parChecker(symbolString):    s = Stack()  # 构造栈    balanced = True  # 匹配标志 默认为True 表示匹配    index = 0  # 索引 用来取字符    # 当 索引小于字符串的长度 并且 匹配标志为True 时    while index < len(symbolString) and balanced:        # 取字符串当前位的字符        symbol = symbolString[index]        # 如果当前字符属于 左括号集 则入栈        if symbol in '([{':            s.push(symbol)        # 如果当前字符 不是左括号(那当前就是右括号)        else:            # 并且栈是空的            if s.isEmpty():                # 匹配标志设置为 False 表示匹配失败(孤零零的右括号)                balanced = False            # 栈不是空的 拿出栈顶的左括号进行类型匹配            else:                top = s.pop()                # 类型匹配失败                if not matches(top, symbol):                    balanced = False        # 索引向后移动一位        index = index + 1    # 循环结束 如果匹配成功 并且 栈空了    if balanced and s.isEmpty():        return True    else:        return Falsedef matches(left, right):    lefts = "([{"    rights = ")]}"    # 调用字符串的index方法,index() 方法查找指定值的首次出现,并返回索引。    # 左右索引对应,表明符号匹配    return lefts.index(left) == rights.index(right)

测试结果如下图所示:

Python数据结构与算法中的栈怎么实现

以上两个例子说明,在处理编程语言的语法结构时,是十分重要的数据结构。几乎所有记法都有某种需要正确匹配和嵌套的符号。除此之外,栈在计算机科学中还有其他一些重要的应用场景,让我们继续探索。

到此,关于“Python数据结构与算法中的栈怎么实现”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注编程网网站,小编会继续努力为大家带来更多实用的文章!

--结束END--

本文标题: Python数据结构与算法中的栈怎么实现

本文链接: https://www.lsjlt.com/news/324335.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • Python数据结构与算法中的栈怎么实现
    这篇文章主要介绍“Python数据结构与算法中的栈怎么实现”,在日常操作中,相信很多人在Python数据结构与算法中的栈怎么实现问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Python数据结构与算法中的栈怎...
    99+
    2023-06-29
  • Python数据结构与算法中的栈怎么构建
    本篇内容主要讲解“Python数据结构与算法中的栈怎么构建”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Python数据结构与算法中的栈怎么构建”吧!什么是栈栈有时也被称作“下推栈”。它是有序集...
    99+
    2023-06-29
  • Python数据结构与算法中的栈详解
    目录0. 学习目标1. 栈的基本概念1.1 栈的基本概念1.2 栈抽象数据类型1.3 栈的应用场景2. 栈的实现2.1 顺序栈的实现2.1.1 栈的初始化2.1.2 求栈长2.1.3...
    99+
    2024-04-02
  • Python数据结构与算法中的栈详解(1)
    目录什么是栈构建一个栈总结什么是栈 栈有时也被称作“下推栈”。它是有序集合,添加操作和移除操作总发生在同一端,即栈的 “顶端&rdquo...
    99+
    2024-04-02
  • Python数据结构与算法中的栈详解(2)
    目录匹配括号匹配符号总结匹配括号 接下来,我们使用栈解决实际的计算机科学问题。​ 比如我们都写过这样所示的算术表达式, ( 5 + 6 ) ∗ ( 7 + 8 ) / ...
    99+
    2024-04-02
  • Python数据结构与算法中的栈详解(3)
    目录前序、中序和后序表达式是什么?我们为什么要学习前/后序表达式?从中序向前序和后序转换用Python实现从中序表达式到后序表达式的转换​计算后序表达式总结前序、中序和后序表达式是什...
    99+
    2024-04-02
  • JavaScript数据结构与算法之栈实例分析
    这篇文章主要介绍了JavaScript数据结构与算法之栈实例分析的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇JavaScript数据结构与算法之栈实例分析文章都会有所收获,下面我们一起来看看吧。1.认识栈栈:...
    99+
    2023-07-02
  • JavaScript数据结构与算法之栈详解
    目录1.认识栈2.面向过程方法源码编写栈2.1思考2.2需要实现的方法2.3源码实现,并调用类3.用面向对象的方法来源码书写3.1思考3.2需要实现的方法3.3源码及使用类4.总结1...
    99+
    2024-04-02
  • Java数据结构之栈与综合计算器的实现
    目录1.栈1.1 栈的简介1.2 使用数组模拟栈1.3 栈的测试2.综合计算器的实现2.1 需求简介2.2 详细思路及分步图解2.3 完整代码及测试1.栈 1.1 栈的简介 栈(st...
    99+
    2022-11-13
    Java 栈 综合计算器 Java 栈 Java 综合计算器
  • 用Python实现数据结构之栈
    栈是最简单的数据结构,也是最重要的数据结构。它的原则就是后进先出(LIFO),栈被使用于非常多的地方,例如浏览器中的后退按钮,文本编辑器中的撤销机制,接下来我们用Python来具体实现这个数据结构。 栈中的方法 作为一个栈(用S来表示...
    99+
    2023-01-30
    数据结构 Python
  • python数据结构与算法(3)
    Python内置类型性能分析 timeit模块timeit模块可以⽤来测试⼀⼩段Python代码的执⾏速度。class timeit.Timer(stmt='pass', setup='pass', ...
    99+
    2023-01-31
    数据结构 算法 python
  • 【数据结构】Java实现栈
    目录 1. 概念 2. 栈的使用  3. 自己动手实现栈(使用动态数组实现栈)  1. 创建一个MyStack类 2. push入栈 3. pop出栈 4. 查看栈顶元素 5. 判断栈是否为空与获取栈长 6. toString方法 4. 整...
    99+
    2023-10-27
    数据结构 jvm java
  • Java 数据结构与算法系列精讲之栈
    目录概述栈栈实现push方法pop方法main完整代码概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 栈 栈 (Stack) 是一种运算受限...
    99+
    2024-04-02
  • Python数据结构-----栈1.0(栈的介绍与操作)
    目录 前言: 栈的介绍 Python栈的操作 1.创建栈 2.判断栈是否为满  3.判断栈是否为空  4.压栈 5.出栈 6.展示栈数据 7.获取到栈顶的数据 8.获取到栈的数据总数 第三方模块实现栈 下载模块: 导入模块:  使用示例: ...
    99+
    2023-10-18
    数据结构 链表 java python 高级编程
  • Python数据结构的栈实例分析
    这篇文章主要介绍“Python数据结构的栈实例分析”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“Python数据结构的栈实例分析”文章能帮助大家解决问题。1. 栈的基本概念1.1 栈的基本概念栈 (...
    99+
    2023-06-29
  • 【数据结构与算法】堆的实现(附源码)
      目录 一.堆的概念及结构 二.接口实现 A.初始化  Heapinit   销毁 Heapdestroy B.插入 Heappush 向上调整  AdjustUp 1.Heappush 2.AdjustUp C.删除 Heappop...
    99+
    2023-09-17
    java 算法 数据结构 c语言
  • 怎么分析Java数据结构中的栈与队列
    今天就跟大家聊聊有关怎么分析Java数据结构中的栈与队列,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。一,栈1,概念在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的。比如你...
    99+
    2023-06-29
  • JavaScript数据结构与栈实例分析
    今天小编给大家分享一下JavaScript数据结构与栈实例分析的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们...
    99+
    2024-04-02
  • 怎么用Java数据结构与算法实现递归与回溯
    这篇文章主要介绍“怎么用Java数据结构与算法实现递归与回溯”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“怎么用Java数据结构与算法实现递归与回溯”文章能帮助大家解决问题。1.什么是递归?简单的说...
    99+
    2023-06-29
  • Python数据结构树与算法分析
    目录1.示例2.术语及定义3.实现3.1 列表之列表3.2节点与引用4.二叉树的应用4.1解析树4.2树的遍历5.利用二叉堆实现优先级队列6.二叉搜索树6.1搜索树的实现7.平衡二叉...
    99+
    2024-04-02
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作