【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式

这篇具有很好参考价值的文章主要介绍了【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言: 

中缀表达式:

 后缀表达式:

中缀表达式转后缀表达式:

后缀表达式计算结果:

总结: 


前言: 

计算机在计算四则运算的时候,由于括号以及运算优先级的存在,并不能够很好的处理所有的运算,为了处理这种情况,我们引入了后缀表达式来优化算法。

中缀表达式:

        中缀表达式是常见的数学表达式表示方法,即操作数位于操作符之间。例如,最常见的中缀算术表达式是 "3 + 4"。中缀表达式有一个显著的特点,就是需要采用运算符优先级来确定表达式的计算顺序。如果表达式中包含不同优先级的运算符,则需要采用约定的优先级规则来计算表达式。在处理中缀表达式时,通常需要将表达式转换为逆波兰表达式或前缀表达式来方便计算。

 后缀表达式:

        逆波兰表达式,又称后缀表达式,是一种数学表达式的表示方法。在逆波兰表达式中,操作符在操作数之后,因此也被称为后缀表示法。例如,表达式 “3 + 4” 在逆波兰表达式中表示为 “3 4 +”。逆波兰表示法可以通过栈来实现,首先将所有操作数入栈,每当遇到一个操作符时,弹出栈顶的两个操作数进行运算,并将运算结果再次压入栈中,直到整个表达式处理完毕。与传统的中缀表达式相比,逆波兰表达式的优点是可以不用考虑运算符优先级的问题。

后缀表达式巧妙地解决了计算机在处理数字运算的时候难处理算数优先级的问题。

中缀表达式转后缀表达式:

转化规则:从左到右遍历中缀表达式中的每个数字和符号,如果是数字就输出,成为后缀表达式的一部分,如果是符号,就判断其与栈顶符号的优先级,是右括号或优先级不高于栈顶符号(乘除优先于加减),则栈顶元素依次出栈并输出,并把当前符号进栈,一直到最后输出后缀表达式为止。

我们以 9+(3-1)*3+10/2 为例:

 第一步:第一个数字是9,直接输出,第二个是+号,进栈

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

 第二步:第三个符号是 ' ( ' ,依然是符号,但是是左括号还没有配对,因此进栈,左括号之后是3,为数字直接输出,三后面是-号,进栈。-号后面是数字1,出栈

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

 第三步:数字1后面是 ‘ )’ ,已经满足我们前面提到的如果是右括号就出栈,因此栈顶依次出栈输出,直到 ‘(’ 出栈为止。

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式 第四步:‘)’ 后面是 ‘ * ’ 号,此时入栈的和栈顶都是符号,就要进行比较,因为*的优先级比+高,因此入栈,‘*’号后面是数字3,直接输出

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

 第五步:数字3后面是‘ + ’号,此时栈顶的 ‘ * ’ 要比‘  +  ’的优先级高,因此栈内的元素全部出栈,‘+’号后面的是数字10,直接输出。需要注意的是此处的+并不是9后面的+,而是3后面的+。

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

 第六步:10后面是‘ / ’号,直接入栈,‘ / ’号后面是2,数字就输出,因为此时这个式子已经结束了,我们就把栈内剩余的符号依次出栈

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

 这样我们就得到了9+(3-1)*3+10/2的后缀表达式:9 3 1 - 3 * + 10 2 / +

后缀表达式计算结果:

我们仍然以9+(3-1)*3+10/2为例,我们已经得到了他的后缀表达式为9 3 1 - 3 * + 10 2 / +。

计算规则:从左到右遍历表达式的每一个数字和符号,如果是数字就进栈,如果是符号,就把处于栈顶的两个数字出栈,进行运算,并让计算结果再次进栈,一直到最终获得结果。

第一步:前三个都是数字,我们安排进栈。

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

第二步:1后面是‘ - ’号,我们就将1出栈作为减数,3作为被减数,计算得到结果2,再把2返回到栈里面。再接着让‘ - ’号后面的3进栈。

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

第三步:3后面是‘ * ’号,我们就再次调出栈内的两个数字相乘,得到结果6,再把6入栈,在后面是‘ + ’号,就把9和6出栈相加,结果为15,再次返回栈中。

 第四步:把后面两个数字10和2压入栈里面,接下来是符号/,就调出栈顶的2和10,10/2=5,再次把5压入栈内

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

 第五步:最后一个符号是‘ + ’号,我们就把栈顶的两个元素5和15拿出来,进行相加,把得到结果的20入栈,此时式子已经计算完毕,就是20,就让20出栈,作为最终运算结果。

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式

总结: 

         逆波兰表达式是一个用来解决计算机识别运算优先级很好的思路,它是对栈的一次高级运用,学习逆波兰表达式可以让我们对于栈的作用更加深刻。

今天的内容到这里就结束了,感谢大家的阅读。

如果我的内容对你有帮助,请点赞,评论,收藏。创作不易,大家的支持就是我坚持下去的动力!

【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式,【夜深人静学数据结构与算法】,开发语言,算法,逆波兰表达式文章来源地址https://www.toymoban.com/news/detail-539194.html

到了这里,关于【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【夜深人静学数据结构与算法 | 第十篇】动态规划

    目录 前言: 动态规划: 常见应用: 解题步骤:  动态规划的简化步骤: 案例: 509. 斐波那契数 - 力扣(LeetCode) 70. 爬楼梯 - 力扣(LeetCode) 62. 不同路径 - 力扣(LeetCode) 总结:         本文我们将为大家讲解一下动态规划的理论知识,并且会讲解几道力扣的经典例题。

    2024年02月11日
    浏览(53)
  • 【夜深人静学数据结构与算法 | 第三篇】 二叉树

    目录  前言:  二叉树: 二叉树的种类:  二叉树的存储方式: 1. 链式存储 2. 数组存储 二叉树的遍历方式 深度优先遍历 广度优先遍历 总结: 本文将会详细的介绍各种常见的树以及相对应的概念,存储方式,遍历方式。树是经典的数据结构,因此我们虽然不能做到手撕各

    2024年02月11日
    浏览(50)
  • 【夜深人静学数据结构与算法 | 第九篇】栈与队列

    目录 ​前言: 栈: 栈的实际应用:  队列: 队列的实际应用: 总结:         栈与队列是我们学习的两个经典的数据结构,这两个数据结构应用广泛,在计算机内有很多底层应用,而很多算法也是依靠栈和队列来实现的,因此我们要想学好数据结构与算法,就要学好栈与

    2024年02月15日
    浏览(45)
  • 【夜深人静学习数据结构与算法 | 第十二篇】动态规划——背包问题

      目录  前言:  01背包问题: 二维数组思路: 一维数组思路: 总结:       在前面我们学习动态规划理论知识的时候,我就讲过要介绍一下背包问题,那么今天我们就来讲解一下背包问题。 在这里我们只介绍 01背包 ,至于分组背包和混合背包这种的已经属于竞赛级别的

    2024年02月12日
    浏览(53)
  • 【夜深人静学数据结构与算法 | 第四篇】手撕二叉树遍历

    目录 前言: 二叉树遍历方式: 手撕前中后序遍历(递归)的三大准备 深度优先搜索:  手撕前中后遍历(递归): 手撕前中后序遍历(迭代): 深度优先搜索: 总结:         今天我们将带领大家手撕二叉树的遍历,本篇会分别讲解深度优先搜索法和广度优先有搜索法下

    2024年02月09日
    浏览(50)
  • 【夜深人静学数据结构与算法 | 第七篇】时间复杂度与空间复杂度

    前言:  引入:  时间复杂度:  案例: 空间复杂度: 案例: TIPS:        总结:         今天我们将来介绍时间复杂度和空间复杂度,我们代码的优劣就是依靠这个在评判,以此为背景,我们诞生出了不少的经典思路:用时间换空间,用空间换取时间。而大多数同学

    2024年02月10日
    浏览(67)
  • 夜深人静学32系列10——GPIO中断/NVIC/EXTI/SYSCFG详解,外部中断控制LED

    上期我们学习了GPIO驱动数码管/蜂鸣器/LED和按键等外设,本期我们一起来学习STM32中断的相关内容 当CPU正在处理某个事件的时候,外界发生了紧急事件请求,CPU需要暂停当前的工作,转而去处理这个紧急事件,处理完之后,再次回到之前被中断的地方,继续执行原来的工作,

    2024年01月16日
    浏览(50)
  • 数据结构基础内容-----第二章算法

    算法 是指,解决问题或执行任务的一系列步骤、规则或指令的有序集合。它可以用来解决各种不同的问题,例如搜索、排序、优化、图像和语音识别等。在计算机科学中,算法通常用于编写程序以实现特定任务。算法可以被用于各种不同的领域,如人工智能、机器学习、数据

    2024年02月06日
    浏览(50)
  • [ 数据结构 -- 手撕排序算法第二篇 ] 冒泡排序

    手撕排序算法系列之:冒泡排序。 从本篇文章开始,我会介绍并分析常见的几种排序,大致包括 插入排序 , 冒泡排序 ,希尔排序,选择排序,堆排序,快速排序,归并排序等。 大家可以点击此链接阅读其他排序算法:排序算法_大合集(data-structure_Sort) 本篇主要来手撕冒

    2024年02月11日
    浏览(59)
  • C++算法之旅、05 基础篇 | 第二章 数据结构

    常用代码模板2——数据结构 - AcWing 使用结构体指针,new Node() 非常慢,创建10万个节点就超时了,做笔试题不会用这种方式(优化是提前初始化好数组,但这样跟数组模拟没区别了,而且代码量很长) 使用两个数组,e存储val,ne存储next。空节点next用-1表示 826. 单链表 - AcWi

    2024年02月10日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包