数据结构之栈的应用(算术计算)
栈的应用实战2-->算术计算
问题的提出:计算机的本质工作就是做数学运算,那计算机可以读入字符串“9 + (3 - 1) * 5 + 8 / 2”并计算值吗?
波兰科学家在20世纪50年代提出了一种将运算符放在数字后面的后缀表达式。对应的,我们习惯的数学表达式叫做中缀表达式。
由于中缀表达式符合人类的阅读和思维习惯,后缀表达式符合计算机的“运算习惯”,所以为了计算机能够读入字符串并计算出数值,我们需要将中缀表达式转换成后缀表达式。
那么问题就出现了,如何将中缀表达式转换成后缀表达式?
实例:
5 + 3 => 5 3 +
1 + 2 * 3 => 1 2 3 * +
9 + ( 3 – 1 ) * 5 => 9 3 1 – 5 * +
当然了,办法总比问题多,就这样,中缀表达式转换成后缀表达式的算法就应运而生了。
解决方案:
1.遍历中缀表达式中的数字和符号;
1.1.对于数字:直接输出;
1.2.对于符号;
1.2.1.左括号:进栈;
1.2.2.符号:与栈顶符号进行优先级比较;
1.2.2.1.栈顶符号优先级低:即比栈顶符号优先级高,进栈;
1.2.2.2.栈顶符号优先级不低:即比栈顶符号优先级低,
将栈顶符号弹出并输出,之后进栈;
1.2.3.右括号:将栈顶符号弹出并输出,直到匹配左括号。
2.遍历结束:将栈中的所有符号弹出并输出。
算法框架:
实现代码下载地址:http://download.****.net/download/u014754841/10244007
这里只是实现了中缀表达式转换成后缀表达式转换,计算机算术计算还没真正开始,计算机是如何基于后缀表达式计算的?
计算机对后缀表达式的运算是基于栈的,所以我们还得为计算机的计算再创建一个栈。
计算机基于后缀表达式计算的解决方案
1.遍历后缀表达式中的数字和符号
1.1.对于数字:进栈;
1.2.对于符号:
1.2.1.从栈中弹出右操作数;
1.2.2.从栈中弹出左操作数;
1.2.3.根据符号进行运算;
1.2.4.将运算结果压入栈中。
2.遍历结束:栈中的唯一数字为计算结果。
算法框架
后缀计算实现代码下载地址:http://download.****.net/download/u014754841/10244015
再次唠叨一下,作个总结:
1.中缀表达式是人习惯的表达方式。
2.后缀表达式是计算机喜欢的表达方式。
3.通过栈可以方便的将中缀形式变换为后缀形式。
4.中缀表达式的计算过程类似程序编译运行的过程。
到此,虽有中缀表达式转换成后缀表达式的代码,也有后缀表达式计算的代码,但是离输入算术表达式到计算出结果还有一定的路程需要去趟。要想实现算术计算,还需将这两个算法糅合到一起才可。详请见实例代码。
整体代码下载地址:http://download.****.net/download/u014754841/10244031
控制台小程序下载地址:http://download.****.net/download/u014754841/10244045