目录
1.前言
2.步骤
3.代码实现
4.测试
5.运行结果
6.一些思考
7.一些应用示例
1.前言
掌握堆栈的基本原理 掌握堆栈的存储结构 掌握堆栈的进栈、出栈；
判断栈空的实现方法 掌握应用堆栈实现括号匹配的原理和实现方法；
熟悉python语言编程 熟练使用python语言实现堆栈的进栈Push、插入Pop、判断栈空等操作 熟练使用堆栈实现括号匹配算法。
2.步骤
1、问题描述 一个算术表达式中包括圆括号、方括号和花括号三种形式的括号 编程实现判断表达式中括号是否正确匹配的算法；
2、算法 顺序扫描算术表达式 若算术表达式扫描完成，此时如果栈空，则正确返回(0)；如果栈未空，说明左括号多于右括号，返回(-3) 从算术表达式中取出一个字符，如果是左括号("('或"["或"]")，则让该括号进栈(PUSH) 如果是右括号(")"或"]"或")": （1）、如果栈为空，则说明右括号多于左括号，返回(-2) （2）、如果栈不为空，则从栈顶弹出(POP)一个括号。若括号匹配，则转1继续进行判断；否则，说明左右括号配对次序不正确，返回(-1)。
3.代码实现
"""
1、问题描述
一个算术表达式中包括圆括号、方括号和花括号三种形式的括号
编程实现判断表达式中括号是否正确匹配的算法
2、算法
顺序扫描算术表达式
若算术表达式扫描完成，此时如果栈空，则正确返回(0)；如果栈未空，说明左括号多于右括号，返回(-3)
从算术表达式中取出一个字符，如果是左括号( "("或"["或"{" )，则让该括号进栈(PUSH)
如果是右括号( ")"或"]"或"}" ):
（1）、如果栈为空，则说明右括号多于左括号，返回(-2)
（2）、如果栈不为空，则从栈顶弹出(POP)一个括号。若括号匹配，则转1继续进行判断；否则，说明左右括号配对次序不正确，返回(-1)
"""
def stack_rule(str):# 创建一个空栈stack = []# 定义括号配对规则rule_map = {')': '(', ']': '[', '}': '{'}# 去除数字的影响 遍历到数字不用作处理except_int = set(rule_map.values()) # {(,[,{}for char in str:if char in except_int:stack.append(char)elif char in rule_map:if not stack:return -2 # 右括号多于左括号if stack[-1] != rule_map[char]:return -1 # 左右括号配对次序不正确stack.pop()if stack:return -3 # 左括号多于右括号return 0 # 左右括号匹配正确def main():n = int(input().strip())results = []for _ in range(n):# str = input().strip()str = input()result = stack_rule(str)results.append(result)for result in results:print(result)if __name__ == "__main__":main()
4.测试
"""
3、输入
第一行：样本个数，假设为n。
第二到n+1行，每一行是一个样本（算术表达式串），共n个测试样本。
4、输入样本
4
[[(1+2)3]-1]
[[(1+2]3)-1]
(1+2)3)-1]
[[(1+2)3-1]
5、输出
共有n行，每一行是一个测试结果，有四种结果：
0:左右括号匹配正确 [[(1+2)3]-1]
-1:左右括号配对次序不正确 [[(1+2]3)-1]
-2：右括号多于左括号 (1+2)3-1]
-3：左括号多于右括号 [[(1+2)3-1]
6、输出样本
0
-1
-2
-3
"""
5.运行结果
6.一些思考
本次实验通过实现一个括号匹配算法，深入理解了堆栈数据结构的应用。实验基于Python语言，实现了堆栈的创建、进栈、出栈等基本操作，并将其应用于括号匹配问题。实验结果表明，堆栈结构能够高效地解决括号匹配问题。通过顺序扫描算术表达式，将左括号进栈，右括号出栈并进行匹配，可以准确地判断括号是否正确匹配。在实现过程中，通过设置集合来过滤数字等无关字符，进一步优化了算法的效率。
堆栈作为一种基本的数据结构，在实际应用中具有广泛的价值。例如，在编译器的语法分析中，堆栈用于管理符号表和语法规则的匹配；在函数调用中，堆栈用于保存函数的调用上下文和返回地址；在浏览器的前进后退功能中，堆栈用于记录用户访问的页面历史。此外，堆栈还在深度优先搜索（DFS）、回溯算法以及表达式求值等领域发挥着重要作用。
通过本次实验，进一步加深了对堆栈数据结构的理解。堆栈的“后进先出”（LIFO）特性使其非常适合处理需要反向操作的问题。例如，在表达式求值中，堆栈可以用于管理操作符和操作数的顺序，从而实现中缀表达式到后缀表达式的转换以及后续的计算。在人工智能领域，堆栈可以用于管理搜索路径或状态空间；在游戏开发中，堆栈可以用于实现撤销操作或状态回滚功能。
7.一些应用示例
在编译器的语法分析中，堆栈用于管理符号表和语法规则的匹配
# 示例：使用堆栈检查代码中的括号是否匹配def is_balanced(code):stack = []brackets = {')': '(', '}': '{', ']': '['}for char in code:if char in brackets.values(): # 左括号入栈stack.append(char)elif char in brackets: # 右括号匹配if not stack or stack.pop() != brackets[char]:return Falsereturn not stack # 栈为空则匹配成功# 测试 code_snippet = "def func() { return (1 + 2) * [3 - 4]; }" print(is_balanced(code_snippet)) # 输出: True
在函数调用中，堆栈用于保存函数的调用上下文和返回地址
# 示例：模拟函数调用栈def function_a():print("Function A called")function_b()print("Function A finished")def function_b():print("Function B called")function_c()print("Function B finished")def function_c():print("Function C called")# 模拟调用栈 call_stack = [] call_stack.append("function_a") function_a() call_stack.pop() print("Call stack:", call_stack) # 输出: Call stack: []
在浏览器的前进后退功能中，堆栈用于记录用户访问的页面历史
# 示例：使用堆栈实现浏览器的前进后退功能class BrowserHistory:def __init__(self):self.back_stack = []self.forward_stack = []def visit(self, url):self.back_stack.append(url)self.forward_stack = [] # 清空前进栈print(f"Visited: {url}")def back(self):if len(self.back_stack) > 1:self.forward_stack.append(self.back_stack.pop())print(f"Back to: {self.back_stack[-1]}")else:print("Cannot go back further.")def forward(self):if self.forward_stack:self.back_stack.append(self.forward_stack.pop())print(f"Forward to: {self.back_stack[-1]}")else:print("Cannot go forward further.")# 测试 browser = BrowserHistory() browser.visit("google.com") browser.visit("youtube.com") browser.visit("github.com") browser.back() # 输出: Back to: youtube.com browser.back() # 输出: Back to: google.com browser.forward() # 输出: Forward to: youtube.com
在人工智能领域，堆栈可以用于管理搜索路径或状态空间
# 示例：使用堆栈实现深度优先搜索（DFS）def dfs(graph, start):visited = set()stack = [start]while stack:node = stack.pop()if node not in visited:print(f"Visited: {node}")visited.add(node)stack.extend(reversed(graph[node])) # 将邻居节点逆序入栈# 测试 graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': [] } dfs(graph, 'A') # 输出: # Visited: A # Visited: B # Visited: D # Visited: E # Visited: F # Visited: C
在游戏开发中，堆栈可以用于实现撤销操作或状态回滚功能
# 示例：使用堆栈实现游戏状态的撤销功能class GameState:def __init__(self):self.state_stack = []def save_state(self, state):self.state_stack.append(state)print(f"State saved: {state}")def undo(self):if self.state_stack:previous_state = self.state_stack.pop()print(f"Undo to: {previous_state}")else:print("No states to undo.")# 测试 game = GameState() game.save_state("Level 1") game.save_state("Level 2") game.save_state("Level 3") game.undo() # 输出: Undo to: Level 3 game.undo() # 输出: Undo to: Level 2 game.undo() # 输出: Undo to: Level 1 game.undo() # 输出: No states to undo.
