只要问题满足“后进先出”的特点&＃xff0c;都可以使用栈来解决。数制转换和表达式求值是栈的典型应用&＃xff0c;结合视频理解其算法原理和算法步骤。

1.数制转换

数值进位制的换算是计算机实现计算和处理的基本问题。比如将十进制数m转换为n进制的数&＃xff0c;最常用的算法是除n取余法。这种方法是将十进制数m每次除以n&＃xff0c;直到商为0时为止。将所得的余数依次进栈&＃xff0c;然后按“后进先出”的次序出栈便得到转换结果。其基本原理是&＃xff1a;

m&＃61;(m / n)* n &＃43; m % n ( 其中&＃xff1a; / 为整除&＃xff0c;%为求余 )

例 将十进制数1567转换为八进制数。

设m&＃61;1567 &＃xff0c;n&＃61;8。按照除8取余法&＃xff0c;转换方法和结果如下&＃xff1a;

按照上述除8取余法&＃xff0c;得到的余数依次是7&＃xff0c;3&＃xff0c;0&＃xff0c;3。在转换过程中每得到一个余数则进栈保存&＃xff0c;最先得到的余数7在栈底&＃xff0c;最后得到的余数3在栈顶&＃xff0c;转换完毕后依次出栈&＃xff0c;其输出顺序与计算顺序正好相反&＃xff0c;为3、0、3、7。数值3037即为转换后的八进制数&＃xff0c;可表示为&＃xff1a;

(1567)10 &＃61;(3037)8

将十进制数转换为n进制数的过程中&＃xff0c;计算顺序与输出顺序正好相反。因此&＃xff0c;利用栈解决这个问题是很合适的。

算法原理&＃xff1a;

(1)逐次计算得到相关结果&＃xff0c;先计算得到的结果后输出&＃xff1b;

(2)把逐次得的余数依次进栈&＃xff0c;计算结束后依次出栈。

算法要点(采用顺序栈)&＃xff1a;

(1)m!&＃61;0 &＃xff0c;m%n 的余数进栈&＃xff1b;

若m&＃61;&＃61;0&＃xff0c;结束求余运算&＃xff0c;依次进行出栈操作&＃xff1b;

(2)m&＃61;m/n&＃xff1b;

(3)重复(1)和(2)。

利用顺序栈将任意的十进制非负整数转换为等价的n进制数输出的完整程序如下 &＃xff1a;

#include#include#define MaxSize 100 /*定义顺序栈所能存储的最多的元素的个数*/typedef int ElemType; /*数据元素类型一般用ElemType表示*/struct SeqStack{ /*顺序栈的类型定义*/　　ElemType data[MaxSize]; /*用data数组存储栈中所有的数据元素*/　　int top; /*用整型变量top指示栈顶元素的位置*/};#include "顺序栈基本操作.c" /*顺序栈的6种运算包含在此文件中*/void transform(int m, int n) /*将一个十进制整数m转换为n进制数输出函数*/{int k; /*用来保存余数*/　　int mm&＃61;m; /*用来保存被转换的十进制数m*/ 　　struct SeqStack S; /*顺序栈的变量定义*/　　InitStack(&S); /*将顺序栈a初始化*/　　while(m!&＃61;0) {　　　k&＃61;m%n; /*将十进制数m除以n进制数的余数存入k*/　　　Push(&S,k); /*将k的值进栈a中*/　　　m&＃61;m/n; /*用m除以n的整数商又赋给m*/　　}　　printf("十进制数 %d 转换为 %d 进制数为&＃xff1a;",mm,n);　　while(!StackEmpty(&S)) { /*元素依次出栈 */　　　k&＃61;Pop(&S,k);　　　printf("%d",k);　　}　　printf("");}/*transform end*/ void main(){　　printf("将十进制数转换为任意进制数实例&＃xff1a;");　　transform(1567,8); /*将十进制数转换为八进制数 */　　transform(1567,6); /*将十进制数转换为六进制数 */　　transform(1567,4); /*将十进制数转换为四进制数 */　　transform(1567,2); /*将十进制数转换为二进制数 */}

上机运行该程序后&＃xff0c;得到的运行结果如下&＃xff1a;

将十进制数转换为任意进制数实例&＃xff1a;

十进制数 1567 转换为 8 进制数为&＃xff1a;3037

十进制数 1567 转换为 6 进制数为&＃xff1a;11131

十进制数 1567 转换为 4 进制数为&＃xff1a;120133

十进制数 1567 转换为 2 进制数为&＃xff1a;11000011111

2.表达式的求值

后缀表达式的求值比较简单&＃xff0c;扫描一遍即可完成。具体做法是&＃xff1a;设置一个栈&＃xff0c;开始时栈为空&＃xff0c;当从左到右扫描表达式时&＃xff0c;若遇到操作数&＃xff0c;则进栈&＃xff0c;若遇到运算符&＃xff0c;则从栈中退出两个操作数&＃xff0c;先退出的放在运算符的右边&＃xff0c;后退出的放在运算符的左边&＃xff0c;然后将运算后的结果再进栈&＃xff0c;直到整个表达式结束。此时&＃xff0c;栈中只有一个元素&＃xff0c;该元素即为运算结果。

例 求后缀表达式12 3 20 4/ * 8-6 * &＃43;的值。

栈的变化情况如表3-1所示&＃xff1a;

表3-1 后缀表达式求值时栈的变化

【算法3-12】 后缀表达式的求值算法int Compute(char * str) /*计算由str所指字符串的后缀表达式的值*/{ /*用顺序栈S存储操作数和中间计算结果&＃xff0c;元素类型为int*/　　struct SeqStack S; /*定义x用于保存操作数&＃xff0c;定义i用于扫描后缀表达式*/　　int x;　　int i&＃61;0;　　InitStack(&S); /*初始化栈S&＃xff0c;预分配5个浮点数空间&＃xff0c;以后自动增长*/　　while(str[i]) { /*扫描后缀表达式中的每个字符&＃xff0c;并进行相应处理*/　　 if(str[i]&＃61;&＃61;&＃39; &＃39;) {i&＃43;&＃43;; continue;} /*扫描到空格字符不做任何处理*/　　 switch(str[i])　　 {　　　　case &＃39;&＃43;&＃39;: /*做栈顶两个元素的加法&＃xff0c;和赋给x*/　　　　　x&＃61;Pop(&s)&＃43;Pop(&S);　　　　　i&＃43;&＃43;; break;　　　　case &＃39;-&＃39;: /*做栈顶两个元素的减法&＃xff0c;差赋给x*/　　　　　x&＃61;Pop(&S); /*弹出减数*/　　　　　x&＃61;Pop(&S)-x; /*弹出被减数并做减法*/　　　　　i&＃43;&＃43;; break;　　　　case &＃39;*&＃39;: /*做栈顶两个元素的乘法&＃xff0c;积赋给x*/　　　　　x&＃61;Pop(&S)*Pop(&S);　　　　　i&＃43;&＃43;; break;　　　　case &＃39;/&＃39;: /*做栈顶两个元素的除法&＃xff0c;商赋给x*/　　　　　x&＃61;Pop(&S); /*弹出除数*/　　　　　if(x!&＃61;0.0)　　　　　　　x&＃61;Pop(&S)/x; /*弹出被除数并做除法*/　　　　　else { /*除数为0时终止运行*/　　　　　　　printf("除数为0!");　　　　　　　exit(1);　　　　　}　　　　　i&＃43;&＃43;; break;　　　　default: /*扫描到的是整数字符串&＃xff0c;生成对应的整数*/　　　　　x&＃61;0; /*利用x保存扫描到的整数*/　　　　　while(str[i]>&＃61;48 && str[i]<&＃61;57) {　　　　　　　x&＃61;x*10&＃43;str[i]-48; i&＃43;&＃43;;　　　　}　　}　　Push(&S,x); 　 /*把扫描转换后或进行相应运算后得到的整数压入栈S中*/ } /*while end*/if(StackEmpty(&S)) { /*若计算结束后栈为空则中止运行*/ 　　printf("后缀表达式格式错!");　　exit(1);}/*若栈中仅有一个元素&＃xff0c;则它就是后缀表达式的值&＃xff0c;否则为出错*/x&＃61;Pop(&S);if(StackEmpty(&S)) return x; else {　　printf("后缀表达式格式错!");　　exit(1);　}}