本課主題： 棧的應用
教學(xué)目的： 掌握棧的應用方法,理解棧的重要作用
教學(xué)重點(diǎn)： 利用棧實(shí)現行編輯,利用棧實(shí)現表達式求值
教學(xué)難點(diǎn)： 利用棧實(shí)現表達式求值
授課內容：
一、棧應用之一：數制轉換
將十進(jìn)制數轉換成其它進(jìn)制的數有一種簡(jiǎn)單的方法：
例：十進(jìn)制轉換成八進(jìn)制：(66)10=(102)8
66/8=8 余 2
8/8=1 余 0
1/8=0 余 1
結果為余數的逆序:102 。先求得的余數在寫(xiě)出結果時(shí)最后寫(xiě)出，最后求出的余數最先寫(xiě)出，符合棧的先入后出性質(zhì)，故可用棧來(lái)實(shí)現數制轉換：
void conversion() {
pSqStack S;
SElemType e;
int n;
InitStack(&S);
printf("Input a number to convert to OCT:\n");
scanf("%d",&n);
if(n<0)
{ printf("\nThe number must be over 0.");
return;}
if(!n) Push(S,0);
while(n){
Push(S,n%8);
n=n/8; }
printf("the result is: ");
while(!StackEmpty(*S)){
Pop(S,&e); printf("%d",e);}
}
請看：數制轉換的C源程序
二、棧應用之二：行編輯
一個(gè)簡(jiǎn)單的行編輯程序的功能是：接受用戶(hù)從終端輸入的程序或數據，并存入用戶(hù)的數據區。允許用戶(hù)輸入出錯時(shí)可以及時(shí)更正?？梢约s定＃為退格符，以表示前一個(gè)字符無(wú)效，@為退行符，表示當前行所有字符均無(wú)效。
例：在終端上用戶(hù)輸入為
whli##ilr#e(s#*s) 應為
while(*s)
void LineEdit() {
pSqStack S,T; char str[1000];
int strlen=0; char e; char ch;
InitStack(&S);
InitStack(&T);
ch=getchar();
while(ch!=EOFILE) {
while(ch!=EOFILE&&ch!='\n') {
switch(ch){
case '#': Pop(S,&ch); break;
case '@': ClearStack(S); break;
default: Push(S,ch); break; }
ch=getchar();
}
if(ch=='\n') Push(S,ch);
while(!StackEmpty(*S)) { Pop(S,&e); Push(T,e); }
while(!StackEmpty(*T)) { Pop(T,&e); str[strlen++]=e; }
if(ch!=EOFILE) ch=getchar();
}
str[strlen]='\0';
printf("\n%s",str);
DestroyStack(S);
DestroyStack(T);
}
請看:行編輯的C源程序
三、棧應用之三：表達式求值
一個(gè)程序設計語(yǔ)言應該允許設計者根據需要用表達式描述計算過(guò)程，編譯器則應該能分析表達式并計算出結果。表達式的要素是運算符、操作數、界定符、算符優(yōu)先級關(guān)系。例：1+2*3有+,*兩個(gè)運算符，*的優(yōu)先級高,1,2,3是操作數。 界定符有括號和表達式結束符等。
算法基本思想：
１首先置操作數棧為空棧，表達式起始符＃為運算符棧的棧底元素；
２依次講稿表達式中每個(gè)字符，若是操作數則進(jìn)OPND棧，若是運算符，則和OPTR棧的棧頂運算符比較優(yōu)先權后作相應操作，直至整個(gè)表達式求值完畢。
char EvaluateExpression() {
SqStack *OPND,*OPTR;
char c,x,theta; char a,b;
InitStack(&OPTR); Push(OPTR,'#');
InitStack(&OPND);
c=getchar();
while(c!='#'||GetTop(*OPTR)!='#') {
if(!In(c,OP)) {Push(OPND,c);c=getchar();}
else
switch(Precede(GetTop(*OPTR),c)) {
case '<': Push(OPTR,c); c=getchar(); break;
case '=': Pop(OPTR,&x); c=getchar(); break;
case '>': Pop(OPTR,&theta);
Pop(OPND,&b); Pop(OPND,&a);
Push(OPND,Operate(a,theta,b));
break;
}
}
c=GetTop(*OPND);
DestroyStack(OPTR);
DestroyStack(OPND);
return c;
}
請看:表達式求值的C源程序
四、總結
棧的先進(jìn)后出、后進(jìn)先出的特性。
聯(lián)系客服
