栈的应用----四则运算,后缀逆波兰表示法(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://scyanting.com/article/dhgjpe.html