第2章 特殊线性表—栈、队列.ppt

2.1 “后缀表达式的求值”案例 【案例说明】 设计一个算法，使用顺序栈计算一个后缀表达式的值。程序运行结果如图 2.1 所示。 【案例目的】 (1) 熟悉栈的特点，注意栈与线性表的异同。 (2) 掌握顺序栈和链栈上实现的进栈、退栈等基本算法。 (3) 熟悉栈的“上溢”和“下溢”的概念及其判别条件。 (4) 能够利用栈设计算法、解决简单的应用问题。 【技术要点】 在控制CPU进行后缀表达式求值时，需要借助栈技术来实现。控制CPU进行后缀表达式求值的基本算法是： 1）让CPU从头到尾扫描后缀表达式中的每一个字符， （1）若遇到的是空格，其为分隔符，不需要任何处理； （2）若遇到的是运算符，则表明它的两个操作数已经在栈中，从栈中取出两个操作数进行相应的运算，并将运算结果压入栈中； （3）若遇到的是数字，其必为操作数的最高位数字字符，这时，需要将该字符及其后面连续的数字字符进行处理，生成一个操作数，并将该操作数压入栈中。 2）如此扫描下去，直到整个表达式结束，这时栈顶元素的值就是整个表达式的计算结果。 【代码及分析】 void Calculate_exp(char exp[ ]) { SqStack S; char ch,num[10]; int i=0,x,x1,x2,k; Init_SqStack(S); while( exp[i] ) { switch( exp[i] ) {/*弹出栈顶两元素作加法运算*/ case +: Pop_SqStack(S,x2); Pop_SqStack(S,x1); x=x1+x2; /*数据入栈*/ Push_SqStack(S,x); i++;break; /*弹出栈顶两元素作除法运算*/ case /: Pop_SqStack(S,x2); Pop_SqStack(S,x1); x=x1/x2; Push_SqStack(S,x); /*数据入栈*/ i++; break; case : /*跳过空格*/ i++; break; default: /*遇到运算数,将其转化为整型数据*/ memset(num,0,10); k=0; while( isdigit(exp[i]) ) /* 23 5×6 8 4/-7×+# */ { num[k++]=exp[i] ; i++;} if( strlen(num)!=0 ) {x=atoi(num);Push_SqStack(S,x);} } } /*栈中只有一个数据,则它就是运算结果*/ if( !Empty_SqStack(S) ) { Pop_SqStack(S,x); if(Empty_SqStack(S)) printf(the result is: %d,x); else /*栈中有多个数据,则出错*/ { printf(expression error!\n); return; } } else /*栈空,则出错*/ { printf(stack is empty!); return;} } 2.1.2 应用扩展 1．数制转换 十进制数 N 和其他 d(d 为 2 、8或16)进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个比较简单的方法是“辗转相除法”。 例如，设 N=1256，d=8，其转换过程见表 2-1。 表 2-1 十进制数与八进制数的转换 算法描述： 1）控制CPU将计算过程中得到的 d 进制数的各位顺序进栈，当 N≥0 时，重复执行如下操作。 (1) 若 N≠0，则将 N%d 压入栈 s 中，执行第 2 步；若 N=0，则入计算余数和入栈结束；