数据结构编程实践20讲(Python版)—03栈

embedded/2024/12/22 1:03:32/

本文目录

    • 03 栈 Stack
      • S1 说明
      • S2 示例
        • 基于列表的实现
        • 基于链表的实现
      • S3 问题：复杂嵌套结构的括号匹配问题
        • 求解思路
        • Python3程序
      • S4 问题：基于栈的阶乘计算VS递归实现
        • 求解思路
        • Python3程序
      • S5 问题：逆波兰表示法(后缀表达式)求值
        • 求解思路
        • Python3程序

往期链接

01 数组02 链表

03 栈 Stack

S1 说明

栈是一种线性数据结构，具有后进先出（LIFO, Last In First Out）的特点。栈的主要操作包括插入（压栈）和删除（弹栈），这些操作只能在栈的顶端进行。

基本操作

  • 压栈（Push）：将一个元素添加到栈顶。
  • 弹栈（Pop）：从栈顶移除并返回一个元素。
  • 查看栈顶元素（Peek/Top）：返回栈顶元素，但不删除它。
  • 检查栈是否为空（IsEmpty）：判断栈中是否还有元素。
  • 获取栈的大小（Size）：返回栈中元素的数量。

性质

  • 后进先出（LIFO）：最后压入栈的元素最先弹出。
  • 只能在栈顶进行操作，无法直接访问栈中间或底部的元素。

S2 示例

基于列表的实现
python">class Stack:def __init__(self):self.items = []  # 使用列表存储栈元素def push(self, item):"""压栈操作"""self.items.append(item)def pop(self):"""弹栈操作"""if not self.is_empty():return self.items.pop()raise IndexError("弹栈失败，栈为空")def peek(self):"""查看栈顶元素"""if not self.is_empty():return self.items[-1]raise IndexError("查看栈顶元素失败，栈为空")def is_empty(self):"""检查栈是否为空"""return len(self.items) == 0def size(self):"""获取栈的大小"""return len(self.items)# 使用示例
if __name__ == "__main__":stack = Stack()stack.push(1)stack.push(2)stack.push(3)print("栈顶元素:", stack.peek())  # 输出 3print("弹出元素:", stack.pop())    # 输出 3print("当前栈大小:", stack.size())  # 输出 2

输出

python">栈顶元素: 3
弹出元素: 3
当前栈大小: 2
基于链表的实现
python">class Node:"""链表节点类"""def __init__(self, value):self.value = value  # 节点存储的值self.next = None    # 指向下一个节点的指针class LinkedListStack:"""基于链表的栈类"""def __init__(self):self.top = None  # 栈顶指针def push(self, value):"""压栈操作"""new_node = Node(value)  # 创建新节点new_node.next = self.top  # 新节点指向当前栈顶self.top = new_node  # 更新栈顶为新节点def pop(self):"""弹栈操作"""if self.is_empty():raise IndexError("弹栈失败，栈为空")popped_value = self.top.value  # 保存栈顶值self.top = self.top.next  # 更新栈顶为下一个节点return popped_value  # 返回弹出的值def peek(self):"""查看栈顶元素"""if self.is_empty():raise IndexError("查看栈顶元素失败，栈为空")return self.top.value  # 返回栈顶值def is_empty(self):"""检查栈是否为空"""return self.top is None  # 栈顶指针为空则栈为空def size(self):"""获取栈的大小"""count = 0current = self.topwhile current:count += 1current = current.nextreturn count# 使用示例
if __name__ == "__main__":stack = LinkedListStack()stack.push(10)stack.push(20)stack.push(30)print("栈顶元素:", stack.peek())  # 输出 30print("弹出元素:", stack.pop())    # 输出 30print("当前栈大小:", stack.size())  # 输出 2print("栈是否为空:", stack.is_empty())  # 输出 False# 弹出剩余元素print("弹出元素:", stack.pop())    # 输出 20print("弹出元素:", stack.pop())    # 输出 10print("栈是否为空:", stack.is_empty())  # 输出 True

输出

python">栈顶元素: 30
弹出元素: 30
当前栈大小: 2
栈是否为空: False
弹出元素: 20
弹出元素: 10
栈是否为空: True

S3 问题：复杂嵌套结构的括号匹配问题

‌括号匹配问题‌是一个在算法和数据结构中常见的问题，主要目标是通过检查输入的括号序列是否平衡和闭合，以确定它们是否匹配。这个问题涉及到各种类型的括号，如圆括号、花括号和大括号。

括号匹配问题的核心在于检查输入的括号序列中的左括号和右括号是否能够正确配对，并且配对的顺序是否正确。例如，在算术表达式中，需要确保每一个左括号（如“(”或“[”）都有一个相应的右括号（如“)”或“]”）来闭合它，并且这些括号必须按照正确的顺序闭合。如果输入的括号序列无法满足这些条件，则称该序列不匹配。

要判断的括号字符串：

python">expressions = ["({[()]}{[()]})",  # 匹配"{([()][()])}{[()]()}",  # 匹配"({[()]}{[(])})",  # 不匹配"({[()]}([]{}))"  # 不匹配
]
求解思路
  • 使用一个栈（用Python的列表实现）来跟踪开放的括号。
  • 定义开放括号和闭合括号的集合，以及一个配对字典。
  • 遍历输入字符串中的每个字符：
    • 如果是开放括号，将其推入栈中。
    • 如果是闭合括号，检查栈是否为空（如果为空，则不平衡），然后检查栈顶元素是否与当前闭合括号匹配。如果匹配，则弹出栈顶元素；如果不匹配，则表达式不平衡。
  • 最后，如果栈为空，则表达式平衡；否则不平衡。
Python3程序
python">def is_balanced(expression):# 初始化一个空栈，用于存储开放括号stack = []# 定义开放括号的集合opening = "({["# 定义闭合括号的集合closing = ")}]"# 定义括号对应关系的字典pairs = {")": "(", "}": "{", "]": "["}# 遍历表达式中的每个字符for char in expression:# 如果是开放括号，将其压入栈中if char in opening:stack.append(char)# 如果是闭合括号elif char in closing:# 如果栈为空，说明闭合括号没有对应的开放括号，返回Falseif not stack:return False# 如果栈顶的开放括号与当前闭合括号匹配if stack[-1] == pairs[char]:# 弹出栈顶元素stack.pop()else:# 如果不匹配，返回Falsereturn False# 遍历结束后，如果栈为空，说明所有括号都匹配，返回True；否则返回Falsereturn len(stack) == 0# 测试样例
expressions = ["({[()]}{[()]})",  # 匹配"{([()][()])}{[()]()}",  # 匹配"({[()]}{[(])})",  # 不匹配"({[()]}([]{}))"  # 不匹配
]# 遍历所有测试样例
for expr in expressions:# 调用is_balanced函数检查是否平衡，并打印结果print(f"'{expr}'是{'匹配的' if is_balanced(expr) else '不匹配的'}")

输出

python">'({[()]}{[()]})'是匹配的
'{([()][()])}{[()]()}'是匹配的
'({[()]}{[(])})'是不匹配的
'({[()]}([]{}))'是匹配的

S4 问题：基于栈的阶乘计算VS递归实现

求解思路

使用栈实现的非递归版本。它的工作原理如下：

  • 初始化一个栈和结果变量。
  • 将初始值n压入栈中。
  • 当栈不为空时，循环处理：
    • 弹出栈顶元素。
    • 如果是0或1，直接继续（因为0!和1!都等于1）。
    • 否则，将当前值乘到结果中，并将下一个要处理的值（当前值-1）压入栈中。
  • 循环结束后，返回最终结果。
Python3程序
python"># 递归版本的阶乘计算
def factorial_recursive(n):if n == 0 or n == 1:return 1else:return n * factorial_recursive(n - 1)# 使用栈的非递归版本的阶乘计算
def factorial_iterative(n):# 初始化一个栈来模拟递归调用stack = []result = 1# 将初始值压入栈中stack.append(n)# 当栈不为空时，继续处理while stack:# 从栈顶取出当前要处理的值current = stack.pop()if current == 0 or current == 1:# 0!和1!的值都是1，不需要further处理continueelse:# 将当前值乘到结果中result *= current# 将下一个要处理的值压入栈中stack.append(current - 1)return result# 测试两个版本的阶乘函数
test_numbers = [100]print("递归版本结果：")
for num in test_numbers:print(f"{num}! = {factorial_recursive(num)}")print("\n非递归版本结果：")
for num in test_numbers:print(f"{num}! = {factorial_iterative(num)}")

输出

python">递归版本结果：
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000非递归版本结果：
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

S5 问题：逆波兰表示法(后缀表达式)求值

逆波兰表示法（Reverse Polish Notation, RPN）是一种数学表达式的表示方式，其中运算符跟在操作数后面。这种表示法的优点是可以不使用括号来明确运算的优先级，因为操作数的顺序和运算符的顺序自然决定了计算的顺序。逆波兰表示法的特点

  • 无括号：在逆波兰表示法中，运算符总是位于操作数之后，因此不需要括号来改变运算顺序。
  • 后进先出（LIFO）原则：通常使用栈来计算逆波兰表达式。操作数被压入栈中，运算符则从栈中弹出操作数进行计算。

为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？原因就在于对计算机而言 中序表达式(中缀表达式，我们常用的数学表达式的表示方式，带有括号，并且有运算优先级) 是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

python">中缀表达式：3 + (51 * 2) - 80 / (4 - 2)
后缀表达式：转换后的形式为 3 51 2 * + 80 4 2 - / -

后缀表达式的计算
从左到右开始读取后缀表达式：
(1) 读到 3，入栈。此时栈：[3]
(2) 读到 51，入栈。此时栈：[3, 51]
(3) 读到 2，入栈。此时栈：[3, 51, 2]
(4) 读到 ∗ * ∗，取出栈顶两个数字进行乘法运算：51 * 2 = 102，结果入栈。此时栈：[3, 102]
(5) 读到 + + +，取出栈顶两个数字进行加法运算：3 + 102 = 105，结果入栈。此时栈：[105]
(6) 读到 80，入栈。此时栈：[105, 80]
(7) 读到 4，入栈。此时栈：[105, 80, 4]
(8) 读到 2，入栈。此时栈：[105, 80, 4, 2]
(9) 读到 − - −，取出栈顶两个数字进行减法运算：4 - 2 = 2，结果入栈。此时栈：[105, 80, 2]
(10) 读到 / / /，取出栈顶两个数字进行除法运算：80 / 2 = 40，结果入栈。此时栈：[105, 40]
(11) 读到 − - −，取出栈顶两个数字进行减法运算：105 - 40 = 65，结果入栈。此时栈：[65]

计算结束，栈中只剩下一个数字，这就是最终结果。因此，表达式 3 51 2 * + 80 4 2 - / - 的计算结果是65。

现在计算下面中缀表达式的后缀表达并求值：
在这里插入图片描述

求解思路
  1. 使用正则表达式将输入字符串分割成 tokens。
python">['(', '-', '5', '+', '3', ')', '*', '2', '-', '4', '/', '(', '2', '-', '√', '(', '16', '-', '2', ')', ')', '+', '3', '^', '2']

遍历 tokens，使用栈来处理运算符和括号。

  1. 定义运算优先级，并根据运算符优先级决定何时将运算符加入输出或压入栈。
python">    def precedence(op):"""定义运算符优先级"""if op in {'+', '-'}:return 1if op in {'*', '/'}:return 2if op == '^':return 3if op == '√':return 4return 0
  1. 将运算符号和数学计算对应起来
python">operators = {'+': lambda x, y: x + y,'-': lambda x, y: x - y,'*': lambda x, y: x * y,'/': lambda x, y: x / y if y != 0 else float('inf'),  # 处理除以零的情况'^': lambda x, y: math.pow(x, y),'√': lambda x: math.sqrt(x) if x >= 0 else float('nan')  # 处理负数开方的情况}
  1. 计算得到的后缀表达式的值
Python3程序
python">import re
import mathdef infix_to_postfix(expression):def precedence(op):"""定义运算符优先级"""if op in {'+', '-'}:return 1if op in {'*', '/'}:return 2if op == '^':return 3if op == '√':return 4return 0def is_operator(token):"""检查token是否为运算符"""return token in {'+', '-', '*', '/', '^', '√'}output = []  # 用于存储后缀表达式stack = []   # 用于临时存储运算符# 使用正则表达式分割表达式为tokentokens = re.findall(r'√|\d+\.?\d*|\+|\-|\*|\/|\^|\(|\)', expression)i = 0while i < len(tokens):token = tokens[i]if token.replace('.', '').isdigit():# 处理数字if i > 0 and (tokens[i-1] == ')' or tokens[i-1].replace('.', '').isdigit()):# 在两个数字或右括号和数字之间插入乘号（处理隐式乘法）while stack and precedence(stack[-1]) >= precedence('*'):output.append(stack.pop())stack.append('*')output.append(token)elif token == '(':# 处理左括号if i > 0 and (tokens[i-1] == ')' or tokens[i-1].replace('.', '').isdigit()):# 在数字和左括号之间插入乘号（处理隐式乘法）while stack and precedence(stack[-1]) >= precedence('*'):output.append(stack.pop())stack.append('*')stack.append(token)elif token == ')':# 处理右括号while stack and stack[-1] != '(':output.append(stack.pop())if stack and stack[-1] == '(':stack.pop()  # 弹出左括号else:raise ValueError("括号不匹配")elif is_operator(token):# 处理运算符if token == '√':# 处理根号if i + 1 < len(tokens) and tokens[i+1] == '(':# 如果根号后面跟着左括号，找到匹配的右括号bracket_count = 1j = i + 2while j < len(tokens) and bracket_count > 0:if tokens[j] == '(':bracket_count += 1elif tokens[j] == ')':bracket_count -= 1j += 1if bracket_count != 0:raise ValueError("括号不匹配")# 递归处理根号内的表达式sub_expr = ''.join(tokens[i+2:j-1])sub_postfix = infix_to_postfix(sub_expr)output.extend(sub_postfix)output.append(token)i = j - 1  # 更新索引到右括号的位置else:# 如果根号后面不是左括号，按普通运算符处理while stack and precedence(stack[-1]) >= precedence(token):output.append(stack.pop())stack.append(token)else:# 处理一元减号if token == '-' and (i == 0 or tokens[i-1] == '(' or is_operator(tokens[i-1])):output.append('0')while stack and precedence(stack[-1]) >= precedence(token):output.append(stack.pop())stack.append(token)i += 1# 将栈中剩余的运算符添加到输出while stack:if stack[-1] == '(':raise ValueError("括号不匹配")output.append(stack.pop())return outputdef evaluate_rpn(tokens):"""计算后缀表达式的值"""stack = []operators = {'+': lambda x, y: x + y,'-': lambda x, y: x - y,'*': lambda x, y: x * y,'/': lambda x, y: x / y if y != 0 else float('inf'),  # 处理除以零的情况'^': lambda x, y: math.pow(x, y),'√': lambda x: math.sqrt(x) if x >= 0 else float('nan')  # 处理负数开方的情况}for token in tokens:if token in operators:if token == '√':# 处理一元运算符（开方）if not stack:raise ValueError("无效的表达式：√ 缺少操作数")a = stack.pop()result = operators[token](a)else:# 处理二元运算符if len(stack) < 2:raise ValueError(f"无效的表达式：{token} 缺少操作数")b = stack.pop()a = stack.pop()result = operators[token](a, b)stack.append(result)else:# 将数字转换为浮点数并压入栈try:stack.append(float(token))except ValueError:raise ValueError(f"无效的token: {token}")# 确保最后栈中只剩一个数（结果）if len(stack) != 1:raise ValueError("无效的表达式")return stack[0]def calculate(expression):"""主计算函数，处理异常并返回结果"""try:postfix = infix_to_postfix(expression)result = evaluate_rpn(postfix)return resultexcept Exception as e:return f"错误: {str(e)}"if __name__ == '__main__':# 测试expressions = '(-5 + 3) * 2 - 4 / (2 - √(16-2)) + 3^2'postfix = infix_to_postfix(expressions)result = evaluate_rpn(postfix)print(f"中缀表达式: {expressions}")print(f"后缀表达式: {' '.join(postfix)}")print(f"计算结果: {result}")

结果

python">中缀表达式: (-5 + 3) * 2 - 4 / (2 - √(16-2)) + 3^2
后缀表达式: 0 5 - 3 + 2 * 4 2 16 2 - √ - / - 3 2 ^ +
计算结果: 7.296662954709577

http://www.ppmy.cn/embedded/121609.html

相关文章

算法种类丰富，分析准确率业内领先的智慧能源开源了

算法种类丰富，分析准确率业内领先的智慧能源开源了

一、简介 AI视频监控平台, 是一款功能强大且简单易用的实时算法视频监控系统。愿景在最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;减少企业级应用约 95%的开发成本&#xff0c;在强大视频算…
阅读更多...
list的模拟实现

list的模拟实现

目录 1.结构 2.用3个类实现list 3.单个节点的定义 4.迭代器的定义 5.list类的实现 6.vector与list的区别 1.结构 list底层是一个带头双向循环链表 2.用3个类实现list 1.链表中的单个节点 2.迭代器 3.list 由于链表中的迭代器已经不是原生指针&#xff0c;所以将迭代…
阅读更多...
【环境配置】科研小白Windows下安装Git

【环境配置】科研小白Windows下安装Git

2024年小白使用Win10安装Git 2.46.2教程&#xff1a; 1 下载安装包 访问下载地址 Git - Downloading Package (git-scm.com) 下载之后打开文件 2 安装过程 点击Next 2.1 选择安装路径 2.2 选择勾选必要组件 2.3 一路Next 这一步直接Next即可 继续点击Next 继续点击Ne…
阅读更多...
算法打卡：第十一章 图论part10

算法打卡：第十一章 图论part10

今日收获&#xff1a;Bellman_ford 队列优化算法&#xff08;又名SPFA&#xff09;&#xff0c;bellman_ford之判断负权回路和单源有限最短路 1. Bellman_ford 队列优化算法&#xff08;又名SPFA&#xff09; 题目链接&#xff1a;94. 城市间货物运输 I (kamacoder.com) 思路…
阅读更多...
在 Qt 项目中使用 spdlog 的全攻略

在 Qt 项目中使用 spdlog 的全攻略

目录 1. 准备工作&#xff1a;安装 spdlog 方法一&#xff1a;使用 CMake 的 FetchContent&#xff08;推荐&#xff09; 方法二&#xff1a;手动下载并添加到项目中 2. 在 Qt 项目中集成 spdlog a. 初始化 spdlog b. 在 Qt 的各个部分使用 spdlog 3. 基本使用示例 4. …
阅读更多...
rabbitmq----数据管理模块

rabbitmq----数据管理模块

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 交换机数据管理管理的字段持久化管理类内存管理类申明交换机删除交换机获取指定交换机 队列数据管理管理的字段持久化管理类内存管理类申明/删除/获取指定队列获取所…
阅读更多...
足球青训俱乐部管理：Spring Boot技术驱动

足球青训俱乐部管理：Spring Boot技术驱动

摘 要 随着社会经济的快速发展&#xff0c;人们对足球俱乐部的需求日益增加&#xff0c;加快了足球健身俱乐部的发展&#xff0c;足球俱乐部管理工作日益繁忙&#xff0c;传统的管理方式已经无法满足足球俱乐部管理需求&#xff0c;因此&#xff0c;为了提高足球俱乐部管理效率…
阅读更多...
【MySQL】基本查询

【MySQL】基本查询

目录 前言1. 插入1.1 指定列插入1.2 全列插入1.3 插入否则更新1.4 替换 2. 查询2.1 select2.1.1 全列查询2.1.2 指定列查询2.1.3 表达式查询2.1.4 结果去重2.1.5 插入查询结果 2.2 where2.2.1 比较和逻辑运算符2.2.2 条件查询 2.3 order by2.4 分页显示 3. 修改3.1 update 4. 删…
阅读更多...
最新文章

Copyright @ 2022~2023