• UID162
  • 登录2018-10-14
  • 粉丝7
  • 发帖46
  • 科研点数1点
优异服役勋章
OODLL 发布于2018-07-21 10:48
3/259

【VC++】算术表达式的最简单的解释-逆波兰表达式

楼层直达

描述:效果

图片:psb.jpg

效果


      算法运行效果在上。没看错,某人的代码就是这样.
论坛好像没有程序设计的板块,有点尴尬。不过没事,反正没事干。然后嘛......这文章的标题到底叫什么还不好讲......对于爱好者,八九成是新的;对于NOI的dalao或者专业程序设计人员,说不定还不怎么滴; 对于某某科技(不讲算法的都不是好教程!!!)的受害者,那八九成也是新的。但是是不是最简单的嘛......这还真得权衡一下,毕竟会者不难难者不会。
好了切入到正题。打开你的Window$,然后找这个东西: Calculator.exe。你知道它是什么了——计算器。没什么大不了的,对吧。但是我们要自己实现一个呢?你会选用某宝上某某科技的“输入一个数字,然后等待输入一个运算符,然后再输入一个数字来进行运算”的BUG算法(为啥?之后会提),还是会去抱树的大腿呢?一个个来看看就是:
    1. 如果你选择了某某科技的算法,那么我个人认为,你深受不佳的编程思路的迫害——那种算法压根无法处理这样的问题:5-2*3。它一定会算错
    2. 如果你选择了第二个,那么我猜八九成看过了一本叫做《编译原理》的书,里面提到的树的确是用来解析表达式的(抽象语法树,简称:AST)。
自然地,第一种方法是不可能使用的,它本身做计算器就会变成BUG。而第二种方法的确可行,但是不觉得有点大材小用了吗?而且好像树的数据结构不是那么的好写,要涉及到孩子、双亲什么的问题。       因此,我介绍第三种方法——后缀表达式,或者叫它:逆波兰表达式,如果你还记得《编译原理》或者是你的那本算法书的内容的话,一定记得它在讲栈的时候被提到过。逆波兰表达式,是1929年波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法,这种表达式没有任何括号并且运算符永远都是在后面的,而且是按照运算符优先级排列的。比如,拿刚刚的那个5 - 2 * 3来看,它对应的逆波兰表达式就是:5 2 3 * -(后面会提到怎么转换),然后,计算过程就是下面这样的(注,我用绿色表示被运算的数据和运算符):
5 2 3 * - => 5 6 - => -1
      看出规律了吗?逆波兰表达式的运算符总是操作的是前面的几个数据。在遇到运算符时,会取出前面的数据,然后进行运算,再把运算的结果放回原来的表达式。直到遍历完整个表达式。       好了那么来伪装一下,假设我们会转换后缀表达式了,然后要对它求值,怎么办?先想五秒钟.........       有一个很简单的思路,就是用,一种非常简单却非常重要的数据结构。为什么说简单呢?因为它只是一个数组(顺序栈...哎复杂了不管不管不管),然后遵循下面的原则:后进先出。我比较喜欢用摞书来比喻栈——最先放的书被压在最底下,最后放的书在最上面。放书的过程就是入栈,当把书拿出来时,我们从顶上开始拿,自然的最后放进去的会最先被拿出来。这个拿书的过程叫做出栈。那么为什么说它是非常重要的呢?这一点很好说明,在看完本文后,我们可以来想一想下面的问题:如果我要开发一款编程语言,那么我该怎么做?相信我,你一定会用到栈的,尤其是函数调用那块。       因此,按照栈的思想,我们就可以把操作数(5; 2; 3)给暂时的存起来,然后遇到运算符的时候再把它弹出来计算,再将计算的结果丢回去。直到整个表达式被遍历完,栈中应该也只有一个结果了——那个就是我们需要的结果。因此,对于5 2 3 *-这个玩意,用这个思路计算就应该是:
1. 一直入栈操作数,直到遇到运算符。现在,我们得到了栈中的数据是:3 2 5。
2. 遇到"*",出栈两个数据(xa = 先出来的3, xb = 后出来的2),然后计算xb * xa(注意,虽然乘法满足交换律,但是我依然把顺序标出来了——栈会把顺序弄反过来,从弹出的数据就可以看出了,它和原表达式是反的(请想想看,为什么?)3. 把xb * xa ( 结果为6)入栈,现在栈中的数据为:6 5 -4. 又遇到操作符"-",一样的,弹出数据:xa = 6, xb = 5,计算xb - xa5. 把结果(-1)入栈,栈中的数据为:-16. 表达式遍历完成,计算结果表明栈中只有一个元素,证明表达式正确。输出结果:-1
       现在明白了吧?下面来演练一下这个表达式的计算:逆波兰表达式=8 9 3 2 --*4 10 2 -*-。用上面的栈的过程试试?如果你计算正确的话,得到的值应该是32。下面请把这个表达式还原成原始表达式,试试?       我个人的代码本身是很早以前做的了,现在功能比较全。但是依然可以看得到上面说的过程(背景的大龙猫?我不知道啊......):

描述:计算过程

图片:1.png

计算过程

      然后,具体实现请开动你的大脑,我相信你可以的。下面再来解决第二个问题——如何构建一个逆波兰表达式。       按照之前的描述,逆波兰表达式的运算符顺序是按照运算优先级排列的。什么是运算符优先级?就是先加减后乘除,如果记不得可以想一下自己是不是把5 - 2 * 3计算出9来过?好继续之前的事情,转换问题。转换的思路多种多样,但是既然之前用了栈,那么我一样用栈来实现看看。比如,对于7+8*2这个表达式,我很快就想到了思路,得到了对应的后缀表达式:
1. 遇到操作数7,输出到后缀表达式(结果数据: 7)

2. 遇到运算符"+",入栈运算符(得到栈的数据:+)

3. 遇到操作数8,输出到后缀表达式(结果数据: 7  8)

4. 遇到运算符"*",入栈运算符(得到栈的数据:*+)

5. 遇到操作数2,输出到后缀表达式(结果数据: 7  8 2)

6. 把运算符栈里面的数据全部出栈
      等等......有问题。这样是顺序遍历啊,哪里来的运算符优先级的事情???
       所以,很明显这种简单的方案压根也不通用。我们继续想一下,对于乘、除、幂啊这种运算,它的运算优先级目前来说是最高的——加减都在它的后面。因此,遇到乘号、除号的时候也要把相同优先级的数据弹出来,直到遇到不是同一个优先级的,或者是括号。当遇到加减号的时候,也是要把同一运算优先级的弹出来,直到遇到不是同一个优先级的,或者是括号。自然地,我们还要考虑栈是不是为空的情况(注,这个过程有点抽象,最好拿笔画一画)。那么,考虑一个很简单的式子,5-(2+3+1),它的构建过程就应该是:
01. 输出到后缀表达式: 5

02. 发现栈是空的,因此不管, 入栈"-"(注意顺序,是先判断后入栈)

03. 入栈"(",注意,为了避免想歪,这里直接声明,"("直接入栈,不管是什么时候。

04. 输出到后缀表达式: 5 2

05. 发现栈不是空的,但是栈顶端的元素是"(",因此不管,入栈"+"。

06. 输出到后缀表达式: 5 2 3

07. 发现栈不是空的,栈顶端的元素是"+"(当前栈数据: + ( -  ),因此出栈,直到遇到"("或者栈空了。得到后缀表达式: 5 2 3 +。入栈"+"

08. 输出到后缀表达式: 5 2 3 +1

09. 发现是右括号,因此一直出栈,直到遇到"("。得到栈数据:-,后缀表达式:5 2 3 +1 +。(入栈")",这个并不会执行,括号只是划分优先级而不是用于计算)

10. 遍历完成,弹出栈中所有的数据,得到了5 2 3 +1 +-。执行完毕。
      总结一下,就是遇到操作数直接输出,然后遇到运算符就放入栈中,并按照一定的顺序出栈即可。但是,注意判断和入栈的顺序问题。下面演练一下:7+8*(9-(3+2))【结果:7 8 9 3 2 +-*+】,8*(9-(3-2))-(4*(10-2))【结果: 8 9 3 2 --*4 10 2 -*-】。具体实现嘛......我相信你的。你也可以看我的实现,但是我觉得你可能会头痛——我的实现做了一些拓展,看起来会很烦。

描述:构建过程

图片:2.png

构建过程


       这个,就是算术表达式求值的一种方法的简介。烦请诸位帮忙斧正。
桂棹兮兰桨,击空明兮溯流光。渺渺兮予怀,望美人兮天一方。[url=http://www.arcll.cn/]我的个人网页[/url]欢迎您去看看(论坛不支持UBB???)声明:本人发帖,未注明转载的均为原创。转载务必保留来源
  • UID648
  • 登录2018-10-20
  • 粉丝13
  • 发帖74
  • 科研点数0点
优异服役勋章
二级银心勋章
论坛之星服役勋章
GloomyGhost 发布于2018-07-22 11:23
沙发F
开水来年会吗
<b>DO YOURSELF</b>
  • UID6
  • 登录2018-08-25
  • 粉丝86
  • 发帖274
  • 科研点数4点
高级电子或计算机学者
2016年论坛年会举办者
2018年论坛年会举办者
MT论坛理事会理事
论坛之星服役勋章
追星Maker纪念章
众望瞩目勋章
荣誉会员勋章
优异服役勋章
Maker
叽叽歪 发布于2018-07-22 13:59
板凳F
站长反馈邮箱:YBA@makertime.org
  • UID162
  • 登录2018-10-14
  • 粉丝7
  • 发帖46
  • 科研点数1点
优异服役勋章
OODLL 发布于2018-07-24 08:36
地板F
GloomyGhost:开水来年会吗回到原帖
不了不来了,家里有猫得有人照看
桂棹兮兰桨,击空明兮溯流光。渺渺兮予怀,望美人兮天一方。[url=http://www.arcll.cn/]我的个人网页[/url]欢迎您去看看(论坛不支持UBB???)声明:本人发帖,未注明转载的均为原创。转载务必保留来源
您需要登录后才可以回帖
发表回复

杩斿洖椤堕儴