首页 > 其他分享 >数据结构(3):栈(下)

数据结构(3):栈(下)

时间:2022-11-29 19:34:16浏览次数:38  
标签:return 递归 括号 数据结构 expression stack 表达式


上回说到,栈是只能在某一端进行各种操作的线性表,我们把这一端称之为栈顶,那么另一端就是栈底,其特点为后进先出(LIFO)。这一回,我们来看一下栈的 3 个常见应用:括号匹配、表达式求值外加递归。





数据结构(3):栈(下)_后缀表达式

栈在括号匹配中的应用

数据结构(3):栈(下)_后缀表达式_02


假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序任意即 ([]()) 或 [([][])] 等均为正确的格式,[(]) 或 ([()) 或 (()] 均为不正确的格式。

考虑下列括号序列:

[

(

[

]

[

]

)

]

1

2

3

4

5

6

7

8

分析如下:

  1. 计算机接收第 1 个括号“[”后,期待与之匹配的第 8 个括号出现。
  2. 获得了第 2 个括号“(”后,此时第 1 个括号“[”暂时放在一边,而急迫期待与之匹配的第 7 个括号“)”出现。
  3. 获得了第 3 个括号“[”,此时第 2 个括号“(”暂时放在一边,而急迫与之匹配的第 4 个括号“]”出现。第三个括号的期待得到满足,消解之后,第 2 个括号的期待匹配又成为当前最紧迫的任务。
  4. 以此类推,可见该处理过程与栈的思想吻合。

算法的思想如下:

  1. 初始设置一个空栈,顺序读入括号。
  2. 若是右括号,者或者使置于栈顶的最急迫期待得以消解,或者是不合法的情况(括号序列不匹配,退出程序)。
  3. 若是左括号,则作为一个新的更急迫的期待压入栈中,自然使原有的再战中的所有未消解的期待的急迫性降了一级。算法结束时,栈为空,否则括号序列不匹配。
    算法的实现如下:
def parentheses_matching(parentheses):  # 括号匹配
n = len(parentheses)
if n == 0:
return True
elif n == 1:
return False
stack = Stack()
if parentheses[0] in (')', ']'):
return False
else:
stack.push(parentheses[0])
for bracket in parentheses[1:]:
if stack.get_top() == '(' and bracket == ')':
stack.pop()
elif stack.get_top() == '[' and bracket == ']':
stack.pop()
else:
stack.push(bracket)
return True if stack.stack_empty()else False


数据结构(3):栈(下)_后缀表达式

栈在表达式求值中的应用

数据结构(3):栈(下)_后缀表达式_02


表达式求值是程序设计语言编译中一个最基本的问题,它的实现是栈应用的一个典型范例。中缀表达式不仅依赖运算符的优先级,而且还要处理括号。后缀表达式的运算符在操作数后面,在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和操作符。中缀表达式 A+B*(C-D)-E/F 所对应的后缀表达式为 ABCD-*+EF/-。

将中缀表达式转换为后缀表达式的算法思想如下:

从左向右开始扫描中缀表达式;

遇到数字时,加入后缀表达式;

遇到运算符时:

  1. 若为‘(’,入栈;
  2. 若为‘)’,则依次把栈中的运算符加入后缀表达式,直到出现‘(’,从栈中删除‘(’;
  3. 若为出括号外的其他运算符,当其优先级高于除‘(’外的栈顶运算符时,直接入栈。否则从栈顶开始,依次弹出比当前处理的运算符优先级高和优先级相等的运算符,直到一个比它优先级低的或遇到了一个左括号为止。

当扫描的中缀表达式结束时,栈中的所有运算符依次出栈加入后缀表达式。

通过后缀表达式求值的过程为:顺序扫描表达式的每一项,然后根据它的类型作如下相应操作:若该项是操作数,则将其压入栈中;若该项是操作符<op>,则连续从栈中退出两个操作数 Y 和 X,形成运算指令 X<op>Y,并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后,栈顶存放的就是最后的计算结果。

算法的实现如下:

def isnumber(string):  # 判断为字符串是否可以转换为数,不考虑负数和科学计数法
if string.isdecimal():
return True
strings = string.split('.')
if len(strings) == 2 and strings[0].isdecimal() and strings[1].isdecimal():
return True
return False




def check_priority(o1, o2): # 判断操作符 o2 的优先级是否大于等于操作符 o1 的优先级
return True if o1 in ('+', '-') and o2 in ('*', '/') or o1 in ('+', '-') and o2 in ('+', '-') or o1 in (
'*', '/') and o2 in ('*', '/')else False




def expression_evaluation(infix_expression): # infix_expression:中缀表达式,空格分隔操作数和操作符(含括号),括号全是小括号
infix_expression, postfix_expression, stack = [float(_) if isnumber(
_)else _ for _ in infix_expression.split()], [], Stack()
for e in infix_expression:
if type(e) == float:
postfix_expression.append(e)
elif check_priority(e, stack.get_top()):
while check_priority(e, stack.get_top()):
postfix_expression.append(stack.pop())
stack.push(e)
elif e == ')':
while stack.get_top() != '(':
postfix_expression.append(stack.pop())
stack.pop()
else:
stack.push(e)
while not stack.stack_empty():
postfix_expression.append(stack.pop())
for e in postfix_expression:
if e not in ('+', '-', '*', '/'):
stack.push(e)
else:
y, x = stack.pop(), stack.pop()
if e == '+':
stack.push(x+y)
elif e == '-':
stack.push(x-y)
elif e == '*':
stack.push(x*y)
else:
stack.push(x/y)
return stack.pop()


数据结构(3):栈(下)_后缀表达式

栈在递归中的应用

数据结构(3):栈(下)_后缀表达式_02


递归是一种重要的程序设计方法。简单地说,若一个函数、过程或数据结构的定义中又应用了它自身,则这个函数、过程或数据结构称为是递归定义的,简称递归

它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算,大大减少了程序的代码量。但在通常情况下,它的效率并不是太高。

以斐波那契数列为例,其定义为

数据结构(3):栈(下)_运算符_07

这就是递归的一个典型例子,用程序实现时如下:

def fib(n):  # 斐波那契数列的实现(递归)
if n == 0: # 边界条件
return 0
elif n == 1: # 边界条件
return 1
return fib(n-1)+fib(n-2) # 递归表达式

必须注意递归模型不能是循环定义的,其必须满足下面的两个条件:

  • 递归表达式(递归体)。
  • 边界条件(递归出口)。

递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。

在递归调用过程中,系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储,递归次数过多容易造成栈溢出等。而其效率不高的原因是递归调用过程中包含很多重复的计算。

所以,递归效率低下,但优点是代码简单,容易理解。

可以将递归算法转换为非递归算法,通常需要借助栈来实现这种转换。


数据结构(3):栈(下)_后缀表达式

总结

数据结构(3):栈(下)_后缀表达式_02


关于栈的应用就说到这里,下一回我们看到另一个操作受限的线性表:队列!

当然,我从今年开始已经入驻 B 站了!下面给出 B 站账号:新时代的运筹帷幄,喜欢的可以关注一下,看完视频不要忘记一键三连啊!

今天的文章有不懂的可以后台回复“加群”,备注:Python 机器学习算法说书人,不备注可是会被拒绝的哦~!



数据结构(3):栈(下)_运算符_10


标签:return,递归,括号,数据结构,expression,stack,表达式
From: https://blog.51cto.com/u_15829940/5896592

相关文章

  • 数据结构(4):队列(下)
    上回说到,队列是一个先进先出的操作受限的线性表。这一回,我们看到队列的两个常见的应用:层次遍历和在计算机系统中的应用。队列在层次遍历中的应用在信息处理中有一大类问题需......
  • 数据结构(5):数组
    上一回简单的说了一下队列两个常见的应用:层次遍历以及在计算机系统中的应用,这一回,我们来看一个大家都非常熟悉的数据结构:数组!数组的定义数组是由n(n≥1)个相同类型的数据元素......
  • SQL注入问题、视图、触发器、事务、存储过程、函数、函数、索引相关概念、索引数据结
    目录SQL注入问题视图触发器事务存储过程函数函数索引相关概念索引数据结构慢查询优化测试索引联合索引全文检索插入数据更新数据删除数据主键外键重命名表事务安全管理隔离......
  • C++数据结构和算法:位运算、字符串
    --------------------------------位运算---------------------------------Q1.用位运算交换两个值前提:要交换的两个值是独立内存voidSwap(int&a,int&b){a......
  • 数据结构(1) pair和map使用
         #include<iostream>#include<thread>#include<map>#include<algorithm>#include<vector>#ifdeflniux#include<unistd.h>//usleep(100......
  • 【剑指Offer】数据结构
    文章目录​​励志​​​​一、剑指Offer05.替换空格​​​​题:​​​​解:​​​​二、剑指Offer06.从尾到头打印链表​​​​题:​​​​解:​​​​三、剑指Offer09.......
  • PTA 21级数据结构与算法实验8—排序
    目录7-1统计工龄7-2寻找大富翁7-3点赞狂魔7-4插入排序还是归并排序7-5插入排序还是堆排序7-6逆序对7-7堆排序7-8石子合并7-9第k小7-10快速排序的过程7-1统计工......
  • go源码学习(一):数据结构-数组
    数组是相同类型元素的集合,在内存中对应一块连续的内存空间。数组类型是通过存储的元素类型以及能够存储的大小两个维度来决定的,一旦声明之后大小就不可更改。初始化go语......
  • 【779】R语言数据结构
    1.向量向量从数据结构上看就是一个线性表,可以看成一个数组。c()是一个创造向量的函数。R语言中的"下标"不代表偏移量,而代表第几个,也就是说是从1开始的!seq......
  • 常见8大数据结构
    8种数据结构,数组、链表、栈、队列、树、堆、图、哈希表。①、数组优点:按照索引查询元素的速度很快;按照索引遍历数组也很方便。缺点:数组的大小在创建后就确定......