专栏首页五分钟学算法五分钟小知识之什么是前缀表达式

五分钟小知识之什么是前缀表达式


算术表达式是最常用的表达式,又称为数值表达式。它是通过算术运算符来进行运算的数学公式。

表达式计算 (expression evaluation) 是程序设计语言编译中的一个最基本问题,也是早期计算机语言研究的一项重要成果,它使得高级语言程序员可以使用与数学形式相一致的方式书写表达式。

一般我们接触比较熟悉的是 中缀表达式

中缀表达式是常见的运算表达式,如 ( 3 + 4 ) × 5 - 6 。中缀表达式在我们日常生活中应用最为广泛,也最符合人的计算思维。

今天来科普一下比较不常用的前缀表达式。

前缀表达式

前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前。LeetCode 第 150 号问题就用到了波兰式的概念,具体可以点击了解一下。

例如:中缀表达式 ( 2 + 3 ) × 4 - 5,采用前缀表达式为:- × + 2 3 4 5

前缀表达式运算:

•对前缀表达式进行从右至左依次扫描•当遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈•重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果

例如前缀表达式 : - × + 2 3 4 5

•从右至左扫描,将5、4、3、2压入堆栈•遇到 + 运算符,因此弹出 2 和 3( 2 为栈顶元素,3 为次顶元素,注意与后缀表达式做比较),计算出 2 + 3 的值,得 5,再将 5 入栈;•接下来是 × 运算符,因此弹出 5 和 4 ,计算出 5 × 4 = 20,将 20 入栈•最后是 - 运算符,计算出 20 - 5 的值,即 15,由此得出最终计算结果

中缀表达式转为前缀表达式: 转换步骤如下:

•(1)初始化两个栈:运算符栈 s1,储存中间结果的栈 s2•(2)从右至左扫描中缀表达式•(3)遇到操作数时,将其压入 s2•(4)遇到运算符时,比较其与 s1 栈顶运算符的优先级

•a:如果 s1 为空,或栈顶运算符为右括号 “ ) ”,则直接将此运算符入栈 •b:否则,若优先级比栈顶运算符的较高或相等,也将运算符压入 s1 •c:否则,将 s1 栈顶的运算符弹出并压入到 s2 中,再次转到 ( 4 - 1 ) 与 s1 中新的栈顶运算符相比

•(5)遇到括号时

•a:如果是右括号“)”,则直接压入 s1 •b:如果是左括号“(”,则依次弹出 s1 栈顶的运算符,并压入 s2 ,直到遇到右括号为止,此时将这一对括号丢弃

••(6)重复步骤(2)至(5),直到表达式的最左边••(7)将 s1 中剩余的运算符依次弹出并压入 s2••(8)依次弹出 s2 中的元素并输出,结果即为中缀表达式对应的前缀表达式。

例如:中缀表达式 1 + (( 2 + 3 ) × 4) - 5 转为前缀表达式具体过程,如下图

END

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:进击的HelloWorld

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 五分钟小知识之什么是后缀表达式

    后缀表达式,又称逆波兰式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。

    五分钟学算法
  • 看动画轻松理解「 堆 」

    本文通过堆的实现、最小堆(最大堆)、堆的时间复杂度、优先队列的实现、堆排序来介绍「 堆 」。

    五分钟学算法
  • LeetCode 图解 | 27.移除元素

    给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

    五分钟学算法
  • 使用Kettle模型清洗全国弱口令Top 1000

    前言 几天前,我在FreeTalk北京站演讲了《数据清洗在网络安全中的应用》,由于时间关系,很多内容并没有讲到,会议结束后很多人也私信问我很多问题。其实在这个信...

    FB客服
  • 对python的bytes类型数据split分割切片方法

    以上这篇对python的bytes类型数据split分割切片方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持网站事(zalou.cn...

    砸漏
  • 谦尊升室内定位SDK助力智慧医院APP,实现室内定位导航

    目前上海谦尊升推出的方案就是基于惯性导航的室内定位方案,利用智能手机上的惯性元件进行定位,这是一种自主定位导航的方式,不依赖外界信号也不受其他信号干扰。所以在部...

    BestSDK
  • Java 使用Collections.reverse对list集合进行降序排序

    今天无意中搜了一下Collections.reverse这个方法,结果发现有些人对它的误解蛮深的。下面是一个有百万访问量博主写的,reverse可以对指定列表进...

    我是李超人
  • C语言运算符优先级 详细列表

    文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

    繁花云
  • 上一个电商项目的反思

    加入中科软已经有了一个年头,从去年实习到今年转正,陆陆续续接触了大概四个项目。有电商类,互联网保险类,也经历过管理系统。幸运的是,这些项目都是从零开始,避免了让...

    kirito-moe
  • 电脑已经被智能手机边缘化了,为何其价格屡高不下呢?

    不能简单的认为成边缘化,随着科技的进步,智能手机的作用在加大,相比而言电脑使用的频率在下降,虽然在下降但是整体的总量还是非常巨大,像办公企业方面电脑还是必需品,...

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券