自助网站系统,网页制作与网站建设,徐汇网站建设,建筑360网本文目录 03 栈 StackS1 说明S2 示例基于列表的实现基于链表的实现 S3 问题#xff1a;复杂嵌套结构的括号匹配问题求解思路Python3程序 S4 问题#xff1a;基于栈的阶乘计算VS递归实现求解思路Python3程序 S5 问题#xff1a;逆波兰表示法(后缀表达式)求值求解思路Python3程… 本文目录 03 栈 StackS1 说明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) 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
栈是否为空: TrueS3 问题复杂嵌套结构的括号匹配问题
括号匹配问题是一个在算法和数据结构中常见的问题主要目标是通过检查输入的括号序列是否平衡和闭合以确定它们是否匹配。这个问题涉及到各种类型的括号如圆括号、花括号和大括号。
括号匹配问题的核心在于检查输入的括号序列中的左括号和右括号是否能够正确配对并且配对的顺序是否正确。例如在算术表达式中需要确保每一个左括号如“(”或“[”都有一个相应的右括号如“)”或“]”来闭合它并且这些括号必须按照正确的顺序闭合。如果输入的括号序列无法满足这些条件则称该序列不匹配。
要判断的括号字符串
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! 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000S5 问题逆波兰表示法(后缀表达式)求值
逆波兰表示法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 1if op in {*, /}:return 2if op ^:return 3if op √:return 4return 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 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[i1] (:# 如果根号后面跟着左括号找到匹配的右括号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[i2: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^2postfix 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
