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

往期链接

01 数组	02 链表

03 栈 Stack

S1 说明

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

基本操作

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

性质

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

S2 示例

基于列表的实现

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

输出

栈顶元素: 3
弹出元素: 3
当前栈大小: 2

基于链表的实现

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

输出

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

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

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

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

要判断的括号字符串：

expressions = ["({[()]}{[()]})",  # 匹配"{([()][()])}{[()]()}",  # 匹配"({[()]}{[(])})",  # 不匹配"({[()]}([]{}))"  # 不匹配
]

求解思路

• 使用一个栈（用Python的列表实现）来跟踪开放的括号。
• 定义开放括号和闭合括号的集合，以及一个配对字典。
• 遍历输入字符串中的每个字符：
  • 如果是开放括号，将其推入栈中。
  • 如果是闭合括号，检查栈是否为空（如果为空，则不平衡），然后检查栈顶元素是否与当前闭合括号匹配。如果匹配，则弹出栈顶元素；如果不匹配，则表达式不平衡。
• 最后，如果栈为空，则表达式平衡；否则不平衡。

Python3程序

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 '不匹配的'}")

输出

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

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

求解思路

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

• 初始化一个栈和结果变量。
• 将初始值n压入栈中。
• 当栈不为空时，循环处理：
  • 弹出栈顶元素。
  • 如果是0或1，直接继续（因为0!和1!都等于1）。
  • 否则，将当前值乘到结果中，并将下一个要处理的值（当前值-1）压入栈中。
• 循环结束后，返回最终结果。

Python3程序

# 递归版本的阶乘计算
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)}")

输出

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

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

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

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

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

中缀表达式：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) 读到$\ast$，取出栈顶两个数字进行乘法运算：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。

['(', '-', '5', '+', '3', ')', '*', '2', '-', '4', '/', '(', '2', '-', '√', '(', '16', '-', '2', ')', ')', '+', '3', '^', '2']

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

2. 定义运算优先级，并根据运算符优先级决定何时将运算符加入输出或压入栈。

    def precedence(op):"""定义运算符优先级"""if op in {'+', '-'}:return 1if op in {'*', '/'}:return 2if op == '^':return 3if op == '√':return 4return 0

3. 将运算符号和数学计算对应起来

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')  # 处理负数开方的情况}

4. 计算得到的后缀表达式的值

Python3程序

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}")

结果

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