资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

栈的应用----四则运算,后缀逆波兰表示法(RPN)-创新互联

我们从小就学习四则运算——加减乘除四则。我们也知道,要先乘除后加减,遇到括号要先算括号内的。可是,想让计算机进行这样的四则运算可不容易,它可不知道什么乘除优先,然后加减。那么,该如何让计算机也能进行这样的四则运算呢?就是通过栈。

创新互联是一家专注于网站设计、成都网站制作与策划设计,天等网站建设哪家好?创新互联做网站,专注于网站建设十余年,网设计领域的专业建站公司;建站业务涵盖:天等等地区。天等做网站价格咨询:028-86922220

  我们人类非常熟悉也非常喜欢用中缀表示法进行算数运算,什么是中缀表示法呢?也就是,一个运算符在两个数字中间。比如,5+3,3*5,5/2等等,这些都是中缀表示法。这种表示法很适合人类使用,但是却不适用于计算机,于是,我们就想出了一种适合计算机的表示方式,叫做,后缀表示法,也就是运算符出现在待运算数字的后面。比如,5+3,这种叫做中缀表示法,用后缀表示法就是,5 3 +,这样的方式就是后缀表示法。也就是说,想让计算机进行运算,首先就要把中缀表达式转换成后缀表达式。接着才是对后缀表达式进行运算。

  那么先来讲,中缀表达式转换成后缀表达式是如何通过栈实现的。我们假设有这么一个中缀表达式:

5 + 4 * 6 / ( 3 + 7 ) * 2 + 1

我们遵循这样的一个原则,遇到数字就直接将数字输出,遇到运算符就将运算符压入栈中。如果当前运算符跟栈顶运算符相比,优先级高于栈顶运算符,就将此运算符压入栈中,该运算符成为新的栈顶运算符。换言之,如果该运算符不高于栈顶运算符,则栈顶元素依次出栈,并将当前符号进栈。好了,开始转换。首先是5,所以,我们要将5输出,因为5是数字,遇到数字就直接输出,那么输出为:

5

接着是一个“+”,因为是运算符,所以将运算符入栈。

+

接着,仍然是数字,所以将4输出,

5 4

由于接下来的是一个乘号,所以,要将它与栈顶的运算符进行对比,发现*号优先级高于+号优先级,所以,将*号入栈,这样以来,栈顶元素就为*号。

+ *

由于6也是数字,所以,可以将其输出

5 4 6

接下来,是个关键。因为,接下来的一个符号是/号,所以,当它和*号对比时,发现/号优先级并不高于*号优先级,所以,将栈顶元素依次出栈,也就是

*

所以,目前,输出元素为

5 4 6 *

然后,将/号入栈,此时栈中只有一个符号/

+ /

接着,是一个左括号( ,所以要将(入栈,直到碰到)是将括号内的内容出栈。

+ / (

因为是数字,所以将3出栈

5 4 6 * 3

接着将+号入栈

+ / ( +

接着是一个数字7,很明显,将数字7出栈

5 4 6 * 3 7

这时碰到了),所以要将+出栈,

5 4 6 * 3 7 +

此时,栈中元素为,

+ /

接着是一个*号,将它与/号对比,发现,它不高于*号,所以,将/出栈,然后跟+号对比,发现高于+号,所以,*可以入栈了,所以,输出元素如下:

5 4 6 * 3 7 + /

栈中数据如下:

+ *

接着是一个数字2,将2直接输出

5 4 6 * 3 7 + / 2

接着是一个+号,优先级并不高于*号,也不高于栈底的+号,所以,将栈顶元素依次出栈,

5 4 6 * 3 7 + / 2 * +

然后将该+号入栈,所以,此时栈内元素为

+

当碰到最后一个1的时候,直接将1输出。

5 4 6 * 3 7 + / 2 * + 1

最后了,已经没有元素了,此时,就将栈中的+号输出,所以,最后,后缀表达式为:

5 4 6 * 3 7 + / 2 * + 1 +

  此时,已经将我们人类认识的中缀表达式转换成了机器认识的后缀表达式。那么,此时,就可以开始运算了,运算还是需要借助栈。当碰到数字时,还是需要将数字压入栈,当碰到运算符时,从栈顶将元素取出,并进行运算。比如,5 4 6都是数字,于是,将5 4 6入栈,

5 4 6

接下来碰到了*号,所以,将6取出作为乘数,将4取出作为被乘数,进行相乘运算,4 * 6 = 24,此时,将运算结果24存入栈中。所以,栈中元素为:

5 24

因为3 7都是数字,所以,将3 7保存至栈中。

5 24 3 7

因为接下来碰到了一个+号,所以,将7和3取出,进行3 + 7 = 10的运算,然后将运算结果10放入栈中。

5 24 10

接下来是一个/号,所以,将10取出作为除数,将24取出作为被除数,所以,24 / 10 = 2.4,然后将2.4存入栈中,所以,

5 2.4

接下来,是一个数字2,所以,将2压入栈中

5 2.4 2

然后是一个乘号,所以将2和2.4取出,执行2.4 * 2 = 4.8,将4.8压入栈中

5 4.8

因为接下来是一个+号,所以将5和4.8取出,执行5 + 4.8 = 9.8,此时将9.8入栈

9.8

然后将数字1入栈

9.8 1

最后一个+号,所以将两个数出栈,执行9.8 + 1 = 10.8,最后运算结果为,10.8。到此就完全结束了。

其实,我举的这个例子是有问题的,栈中保存的是类型相同的元素,所以我这个例子举的不好,不过不影响总结计算机执行四则运算的过程。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


标题名称:栈的应用----四则运算,后缀逆波兰表示法(RPN)-创新互联
文章路径:http://cdkjz.cn/article/dhgjpe.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220