C语言:数据结构-数制转换与表达式求值

1.数制转换

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

m=（m / n）* n + m % n ( 其中： / 为整除，%为求余 )

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

设m=1567 ，n=8。按照除8取余法，转换方法和结果如下：

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

（1567）₁₀ =（3037）₈

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

算法原理：

（1）逐次计算得到相关结果，先计算得到的结果后输出；

（2）把逐次得的余数依次进栈，计算结束后依次出栈。

算法要点（采用顺序栈）：

（1）m!=0 ，m%n 的余数进栈；

若m==0，结束求余运算，依次进行出栈操作；

（2）m=m/n；

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

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

	#include<stdio.h>
	#include<stdlib.h>
	#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=m; /*用来保存被转换的十进制数m*/ 
	struct SeqStack S; /*顺序栈的变量定义*/
	InitStack(&S); /*将顺序栈a初始化*/
	while(m!=0) {
	k=m%n; /*将十进制数m除以n进制数的余数存入k*/
	Push(&S,k); /*将k的值进栈a中*/
	m=m/n; /*用m除以n的整数商又赋给m*/
	}
	printf("十进制数 %d 转换为 %d 进制数为：",mm,n);
	while(!StackEmpty(&S)) { /*元素依次出栈 */
	k=Pop(&S,k);
	printf("%d",k);
	}
	printf("\n");
	}/*transform end*/
	 
	void main()
	{
	printf("将十进制数转换为任意进制数实例：\n");
	transform(1567,8); /*将十进制数转换为八进制数 */
	transform(1567,6); /*将十进制数转换为六进制数 */
	transform(1567,4); /*将十进制数转换为四进制数 */
	transform(1567,2); /*将十进制数转换为二进制数 */
	}
	 
	上机运行该程序后，得到的运行结果如下：
	将十进制数转换为任意进制数实例：
	十进制数 1567 转换为 8 进制数为：3037
	十进制数 1567 转换为 6 进制数为：11131
	十进制数 1567 转换为 4 进制数为：120133
	十进制数 1567 转换为 2 进制数为：11000011111

2.表达式的求值

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

例 求后缀表达式12 3 20 4/ * 8-6 * +的值。

栈的变化情况如表3-1所示：

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

后缀表达式的求值算法

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