数据结构教程 第十一课 栈的应用

本课主题： 栈的应用

教学目的： 掌握栈的应用方法,理解栈的重要作用

教学重点： 利用栈实现行编辑,利用栈实现表达式求值

教学难点： 利用栈实现表达式求值

授课内容：

一、栈应用之一：数制转换

    将十进制数转换成其它进制的数有一种简单的方法：

    例：十进制转换成八进制：(66)10=(102)8

    66/8=8 余 2

    8/8=1 余 0

    1/8=0 余 1
结果为余数的逆序:102 。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：

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源程序
二、栈应用之二：行编辑

一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定＃为退格符，以表示前一个字符无效，@为退行符，表示当前行所有字符均无效。
例：在终端上用户输入为
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源程序

三、栈应用之三：表达式求值

一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例：1+2*3有+,*两个运算符，*的优先级高,1,2,3是操作数。 界定符有括号和表达式结束符等。
算法基本思想：
１首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；
２依次讲稿表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。

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源程序

四、总结

栈的先进后出、后进先出的特性。