资源描述：
《数据结构栈的应用本ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈的应用数制转换“除基取余法”算法基于原理除以基数取余数，逆序排列。例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod813481684 168210 2125 202计算顺序输出顺序进制转换算法思想1.初始化一个空栈S；2.当十进制数N非零时，循环执行以下操作：把N与8求余得到的八进制数压入栈S；N更新为N与8的商。3.当栈S非空时，循环执行以下操作：弹出栈顶元素e，然后输出e。voidconversion(){InitStack(S);scanf("%d",&N);while(N)
2、{Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion余数入栈余数出栈括号匹配括号匹配问题1.括号匹配{[()]},((){}),()2.括号不匹配[(]),([()),(()])检验括号匹配的方法：“期待的急迫程度”检查括号匹配算法的设计思想设一栈；遇到左括号则入栈；遇到右括号时，若栈空，则不匹配(右括号太多)，否则，如果栈顶元素与该右括号匹配，则出栈，否则不匹配(括号不配对)。输入结束后，若栈为空，则匹配，否
3、则不匹配(左括号太多)。StatusMatching(){intstate=1;InitStack(S);ch=getchar();while(ch!=‘#’&&state){switch(ch){case‘(‘
4、
5、’[’:{Push(S,ch);break;}case‘)’:{if(!StackEmpty(S)&&GetTop(S)==‘(‘){Pop(S,e);}else{state=0;}break;}case‘]’:{if(!StackEmpty(S)&&GetTop(S)==‘[‘){Pop(S,e);}e
6、lse{state=0;}break;}ch=getchar();}if(StackEmpty(S)&&state)returnOK;elsereturnERROR;}行编辑程序出现的问题每接受一个字符立即存入存储器吗？NO合理的做法设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。用户输入缓存区（用栈模拟）用户数据区入栈出栈假设从终端接受了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：
7、while(*s)putchar(*s++);行编辑程序算法的设计思想设一栈（输入缓冲区）；读入的字符为退格符，则删除栈顶字符；读入的字符为退行符，则清空栈；否则，读入的字符入栈。每处理完一行字符，将栈底到栈顶的字符存入存储器，清空栈，开始进行下一行的字符处理，直到文件结束。voidLineEdit(){InitStack(S);//缓存栈Sch=getchar();while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!=''){switch(ch){case'#':Pop(S,
8、c);break;//重置S为空栈case'@':ClearStack(S);break;default:Push(S,ch);break;}ch=getchar();//接收本行下一个字符}将从栈底到栈顶的字符传送至调用过程的数据区；可以借助另一个辅助栈来完成InitStack(S2);.//辅助栈S2while(!EmptyStack(S)){//从S栈出来，进入S2Pop(S,e);Push(S2,e);}while(!EmptyStack(S2)){Pop(S2,e);将e写入用户数据区}ClearStack
9、(S);ClearStack(S2);if(ch!=EOF)ch=getchar();//读取下一行字符}DestroyStack(S);DestroyStack(S2);}（算术）表达式求值算术表达式的组成操作数（运算对象或运算量）运算符界限符（如圆括号，作用是改变运算次序）常量、变量、函数、表达式单目、双目以+、-、*、/四种运算为例算术表达式的分类根据运算符在表达式中的不同位置中缀表达式后缀表达式前缀表达式例：表达式3*(5–2)3*(5–2)352-**3–52操作数之间的相对次序不变；运算符的相对次序可能不
10、同；中缀式必须有括号信息，否则运算顺序改变；前缀式：无括号；连续出现的两个操作数和在它们之前出现且紧靠它们的运算符构成了一个最小表达式；后缀式：无括号；运算符的排列顺序就是计算顺序，每个运算符加上在它之前且紧靠它的两个操作数构成了一个最小表达式。三种表达式的特点中缀表达式求值设置两个工作栈：运算符栈S1和操作数栈S2。S2也放表达式的运算结果。
