接触后缀表达式(逆波兰表示法)

逆波兰表示法的起因
服务器君一共花费了287.293 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

栈的现实应用也很多,我们再来重点讲一个比较常见的应用:数学表达式的求值。

  • 我们小学学数学的时候,有一句话是老师反复强调的,“先乘除,后加减,从左算到右,先括号内后括号外' 这个大家都不陌生。我记得我小时候,天天做这种加减乘除的数学作业,很烦,于是就偷偷拿了老爸的计算器来帮着算答案,对于单纯的两个数的加减乘除,的确是省心不少,我也因此潇洒了一两年。可后来要求要加减乘除,甚至还有带有大中小括号的四则运算,我发现老爸那个简陋的计算器不好使了。比如 9+(3-1)×3+10/2,这是一个非常简单的题目,心算也可以很快算出是20。可就这么简单的题目,计算器却不能在一次输入后马上得出结果,很是不方便。

当然,后来出的计算器就髙级多了,它引入了四则运算表达式的概念,也可以输入括号了,所以现在的00后的小朋友们,更加可以偷懒、抄近路做数学作业了。

现在你已经从小学生变成程序员了,那么在新式计算器中或者计算机中,它是如何实现的呢?如果让你用C语言或其他高级语言实现对数学表达式的求值,你打算如何做?

  • 这里面的困难就在于乘除在加减的后面,却要先运算,而加入了括号后,就变得更加复杂。不知道该如何处理。
  • 仔细观察后发现,括号都是成对出现的,有左括号就一定会有右括号,对于多重括号,最终也是完全嵌套匹配的。这用栈结构正好合适,只有碰到左括号,就将此左括号进找,不管表达式有多少重括号,反正遇到左括号就进栈,而后面出现右括号时,就让栈顶的左括号出栈,期间让数字运算,这样,最终有括号的表达式从左到右巡査一遍,栈应该是由空到有元素,最终再因全部匹配成功后成为空栈的结果。

但对于四则运算,括号也只是当中的一部分,先乘除后加减使得问题依然复杂, 如何有效地处理它们呢?我们伟大的科学家想到了好办法。

20世纪50年代,波兰逻辑学家Jan tukasiewicz,当时也和我们现在的同学们一样,困惑于如何才可以搞定这个四则运算,不知道他是否也像牛顿被苹果砸到头而想到万有引力的原理,或者还是阿基米德在浴缸中洗澡时想到判断皇冠是否纯金的办法,总之他也是灵感突现,想到了一种不需要括号的后缀表达法,我们也把它称为逆波兰(Reverse Polish Notation, RPN)表示。

  • 我想可能是他的名字太复杂了,所以后人只用他的国籍而不是姓名来命名,实在可惜。这也告诉我们,想要流芳百世,名字还要起得朗朗上口才行。这种后缀表示法,是表达式的一种新的显示方式,非常巧妙地解决了程序实现四则运算的难题。

我们先来看看,对于“9+(3-1)*3+10/2”如果要用后缀表示法应该是什么样子:9 3 1-3*+ 10 2/+

这样的表达式称为后缀表达式,叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

  • 显然,这里没有了括号。对于从来没有接触过后缀表达式的同学来讲,这样的表述是很难受的。不过你不喜欢,有机器喜欢,比如我们聪明的计算机。

延伸阅读

此文章所在专题列表如下:

  1. 栈的定义与大概理解
  2. 栈的抽象数据类型ADT
  3. 顺序栈:栈的顺序存储结构
  4. 顺序栈的进栈操作
  5. 顺序栈的出栈操作
  6. 获取顺序栈的栈顶元素
  7. 链栈:栈的链式存储结构
  8. 链栈的进栈操作
  9. 链栈的初始化与遍历
  10. 链栈的出栈操作
  11. 链栈的置空操作与判断链栈是否为空
  12. 为什么要使用栈这种数据结构
  13. 递归,栈的重要应用之一
  14. 栈是如何实现递归的
  15. 接触后缀表达式(逆波兰表示法)
  16. 图解后缀表达式的计算过程
  17. 将中缀表达式转化为后缀表达式
  18. 开始学习队列这个数据结构
  19. 队列的抽象数据类型ADT
  20. 顺序队列:队列的顺序存储结构
  21. 顺序队列的入队操作
  22. 顺序队列的出队操作
  23. 顺序队列置空与判断操作
  24. 队列顺序存储结构的不足
  25. 关于循环队列的一些讲解
  26. 链队列:队列的链式存储结构
  27. 链队列的初始化操作
  28. 链队列的入队操作
  29. 链队列的出队操作
  30. 补完链队列的其它常见操作
  31. 循环队列与链队列的优劣势

本文地址:http://www.nowamagic.net/librarys/veda/detail/2302,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2302

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《Head First设计模式(中文版)》 弗里曼 (作者), 等 (作者)

《Head First设计模式》(中文版)共有14章,每章都介绍了几个设计模式,完整地涵盖了四人组版本全部23个设计模式。前言先介绍这本书的用法;第1章到第11章陆续介绍的设计模式为Strategy、Observer、Decorator、Abstract Factory、Factory Method、Singleton,Command、Adapter、Facade、TemplateMethod、Iterator、Composite、State、Proxy。最后三章比较特别。第12章介绍如何将两个以上的设计模式结合起来成为新的设计模式(例如著名的MVC模式),作者称其为复合设计模式(这是作者自创的名称,并非四人组的标准名词)。

更多计算机宝库...