本文目录
- 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 示例
基于列表的实现
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) == 0
def size(self):
"""获取栈的大小"""
return len(self.items)
# 使用示例
if __name__ == "__main__":
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("栈顶元素:", stack.peek()) # 输出 3
print("弹出元素:", stack.pop()) # 输出 3
print("当前栈大小:", 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 = 0
current = self.top
while current:
count += 1
current = current.next
return count
# 使用示例
if __name__ == "__main__":
stack = LinkedListStack()
stack.push(10)
stack.push(20)
stack.push(30)
print("栈顶元素:", stack.peek()) # 输出 30
print("弹出元素:", stack.pop()) # 输出 30
print("当前栈大小:", stack.size()) # 输出 2
print("栈是否为空:", stack.is_empty()) # 输出 False
# 弹出剩余元素
print("弹出元素:", stack.pop()) # 输出 20
print("弹出元素:", stack.pop()) # 输出 10
print("栈是否为空:", 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:
# 如果栈为空，说明闭合括号没有对应的开放括号，返回False
if not stack:
return False
# 如果栈顶的开放括号与当前闭合括号匹配
if stack[-1] == pairs[char]:
# 弹出栈顶元素
stack.pop()
else:
# 如果不匹配，返回False
return False
# 遍历结束后，如果栈为空，说明所有括号都匹配，返回True；否则返回False
return 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 1
else:
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处理
continue
else:
# 将当前值乘到结果中
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) 读到
∗
*
∗，取出栈顶两个数字进行乘法运算：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。
现在计算下面中缀表达式的后缀表达并求值：
求解思路
- 使用正则表达式将输入字符串分割成 tokens。
['(', '-', '5', '+', '3', ')', '*', '2', '-', '4', '/', '(', '2', '-', '√', '(', '16', '-', '2', ')', ')', '+', '3', '^', '2']
遍历 tokens，使用栈来处理运算符和括号。
- 定义运算优先级，并根据运算符优先级决定何时将运算符加入输出或压入栈。
def precedence(op):
"""定义运算符优先级"""
if op in {'+', '-'}:
return 1
if op in {'*', '/'}:
return 2
if op == '^':
return 3
if op == '√':
return 4
return 0
- 将运算符号和数学计算对应起来
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') # 处理负数开方的情况
}
- 计算得到的后缀表达式的值
Python3程序
import re
import math
def infix_to_postfix(expression):
def precedence(op):
"""定义运算符优先级"""
if op in {'+', '-'}:
return 1
if op in {'*', '/'}:
return 2
if op == '^':
return 3
if op == '√':
return 4
return 0
def is_operator(token):
"""检查token是否为运算符"""
return token in {'+', '-', '*', '/', '^', '√'}
output = [] # 用于存储后缀表达式
stack = [] # 用于临时存储运算符
# 使用正则表达式分割表达式为token
tokens = re.findall(r'√|\d+\.?\d*|\+|\-|\*|\/|\^|\(|\)', expression)
i = 0
while 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 = 1
j = i + 2
while j < len(tokens) and bracket_count > 0:
if tokens[j] == '(':
bracket_count += 1
elif tokens[j] == ')':
bracket_count -= 1
j += 1
if 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<