栈的应用——四则运算表达式

摘要:本文是看《大话数据结构》栈章节的学习总结

正文:

栈的应用——四则运算表达式

栈的应用场景有很多,如浏览器的后退,编辑软件的回退等,今天要谈的是栈的基本应用之四则运算表达式(中缀转后缀表达式)

大家都知道用计算器可以很方便的计算出两数运算的结果,但是如果遇到有优先级的四则运算,计算器又是如何去精确的计算出结果呢?

在20世纪50年代有一个叫Jan Łukasiewicz的波兰数学家想到了一种不需要括号的后缀表达式,我们称为逆波兰表示法 ,逆波兰记法不需要括号来标识操作符的优先级

中缀转后缀表达式

我们平时所用的标准四则运算表达式,如:

150-(7+5)*2+30*2

叫做中缀表达式,因为所有的运算符号都在两个数字之间,现在我们通过使用栈将其转为后缀表达式

规则: 从左到右遍历上面中缀表达式的每个数字符号

  1. 如果是数字则直接输出
  2. 如果是符号则判断与栈顶中的符号优先级,是右括号的或者比栈顶中符号优先级低的依次去括号出栈输出
  3. 否则在栈中等待最后遍历完依次输出

转换过程

  1. 按照上述规则依次遍历150-(7+5)*2+30*2,150是数字直接输出,-号进栈,第三个是左括号也是符号依然进栈,7是数字直接输出,如下图一所示。
  1. 下面接着+号进栈,5输出,接下注意的是右括号,遇到右括号需要匹配前面的左括号,并依次去括号出栈输出(输出了+)。接着*号进栈,2输出,如下图二所示。
  1. 此时栈顶是*,然后+准备进栈,对比发现+优先级低于栈顶,则栈顶元素依次输出,完了后+进栈 。接着30输出,*比栈顶+优先级高,直接进栈不输出,然后2输出。如下图三所示。
  1. 最后遍历结束栈中符号依次输出,最终的后缀表达式结果是150 7 5 + 2 * - 30 2 * +

后缀表达式计算结果

上述结果:150 7 5 + 2 * - 30 2 * +, 可能很多人问转这个有什么用,接下来看的是该后缀表达式的计算过程。

计算规则:从左到右遍历每个数字和符号,遇到数字就进栈,遇到符号将处于栈顶的两个元素出栈并运算,运算结果进栈,一直到最后算出最终结果

  1. 150 7 5依次进栈,+号是符号,将栈顶的 7 5出栈并运算(+),结果是12并进栈,2是数字同样进栈。如下图四所示。
  1. 接着是*号,将栈顶的两个元素运算并重新入栈(12 *2);然后是-号,栈顶两个元素分别是150 24,结果是126入栈;然后数字30 2依次入栈。如下图五所示。
  1. 遍历到*,将栈顶元素30 2运算并重新进栈,最后是+号,所以结果是186出栈,栈变为空。如下图六所示。

上述过程都充分的利用了栈的后进先出特性来处理的,所以该表达式的转换和计算是栈的经典应用之一,对理解栈本身也有很大的帮助~

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

Java中的collection架构总结

collection是java中用来收集对象的。java提供了collection的Api,为了避免出现死记api的情况,为了更好的使用collection,首...

874
来自专栏二进制文集

JDK源码分析 Integer

对于JDK源码分析的文章,仅仅记录我认为重要的地方。源码的细节实在太多,不可能面面俱到地写清每个逻辑。所以我的JDK源码分析,着重在JDK的体系架构层面,具体源...

1143
来自专栏老马说编程

(47) 堆和PriorityQueue的应用 / 计算机程序的思维逻辑

45节介绍了堆的概念和算法,上节介绍了Java中堆的实现类PriorityQueue,PriorityQueue除了用作优先级队列,还可以用来解决一些别的问题,...

19210
来自专栏编码前线

在java中String类为什么要设计成final?

String很多实用的特性,比如说“不可变性”,是工程师精心设计的艺术品!艺术品易碎!用final就是拒绝继承,防止世界被熊孩子破坏,维护世界和平!

912
来自专栏专注研发

poj-1056-IMMEDIATE DECODABILITY(字典)

An encoding of a set of symbols is said to be immediately decodable if no code f...

881
来自专栏Golang语言社区

interface引发的事件真相

流动的水没有形状,漂流的风找不到踪迹,一切代码都了然于心,我们在写代码的时候,总是有一种思维定式陪伴左右,在对事物做判断的时候,往往这种思维定式会往正向或反向做...

3406
来自专栏小詹同学

python | 关于多重继承那些事

继承是面向对象编程的一个重要的方式 ,通过继承 ,子类就可以扩展父类的功能 。和 c++ 一样 ,在 python 中一个类能继承自不止一个父类 ,这叫做 py...

1161
来自专栏java系列博客

java Arrays.aslist用法

1816
来自专栏机器学习入门

POJ 刷题系列:2586. Y2K Accounting Bug

POJ 刷题系列:2586. Y2K Accounting Bug 传送门:2586. Y2K Accounting Bug 题意: 有一个公司由于某个病毒使...

2075
来自专栏web前端教室

javascript 红皮高程(10)

继续string类型的相关知识哈,不细看不知道啊,这JS的知识点真是太细碎了。因为许多知识点都互相交织着,但某些属性却并不是所有的对象都有。例如: 转换字符...

2007

扫码关注云+社区

领取腾讯云代金券