栈的应用举例.ppt

例二、数制转换,例三、括号匹配的检验,例四、迷宫求解,例五、表达式求值,例一、大整数相加,大整数相加,相加从低位开始,输出从高位开始用两个栈保存操作数（大整数）结果保存到结果栈,数制转换的原理为：N=(Ndivd)d+Nmodd,例如：（1348)10转换成(2504)8的运算过程如下：,NNdiv8Nmod8,13481684,168210,2125,202,数制转换,voidconversion()/显示和输入的十进制数对应的八进制数值InitStack(S);scanf(%d,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);/conversion,检验含两种括弧的表达式中括弧匹配的正确性。,如表达式中（）或（）等为正确的匹配，（）或（）或()均为不正确的匹配。,检验括弧匹配的方法可用“按期待的急迫程度进行处理”描述之。,例如,考虑下列括号序列：,(,(,),),可见，括弧匹配也遵循“后进先出”的规律。,如何表示下列“不匹配”的情况？,到来的右括弧非是所“期待”的;,来了一个“不速之客”;,直到结束，也没有等到“期待”的匹配;,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空？若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配,3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余。,boolmatching(charexp,intn)/检测长度为n的字符序列exp中的括弧是否匹配inti=0;mat=true;InitStack(S);while(i=opj=opk，因此中缀式里的任一操作符须等到另一个优先级小于或等于它的操作符出现，才可输出到后缀式。,分析“原表达式”和“后缀式”中的运算符:原表达式:a+bc-d后缀式:abc+d-,如何从原表达式求得后缀式？,从原表达式求得后缀式的规律为：,1)设立暂存运算符的栈;,2)设表达式的结束符为“#”,予设运算符栈的栈底为“#”,3)若当前字符是操作数，则直接发送给后缀式;,4)若当前运算符的优先数高于栈顶运算符，则进栈;,5)否则，退出栈顶运算符发送给后缀式;,6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,从原表达式求得后缀式的规律为：,利用栈将中缀表示转换为后缀表示,使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。为了实现这种转换，需要考虑各操作符的优先级。,优先级操作符1单目-、！2*、/、%3+、-4、=5=、!=6”号与输入流最后的“;”号配对时。,中缀表达式转换为后缀表达式的算法,操作符栈初始化，将结束符#进栈。然后读入中缀表达式字符流的首字符ch。重复执行以下步骤，直到ch=#，同时栈顶的操作符也是#，停止循环。若ch是操作数直接输出，读入下一个字符ch。若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp：,若icp(ch)isp(op)，令ch进栈，读入下一个字符ch。若icp(ch)isp(op)，退栈并输出。若icp(ch)=isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。算法结束，输出序列即为所需的后缀表达式。,a(b(c+d/e)-f)#,#,a,(,b,(,c,+,d,/,e,/,/,+,+,-,f,-,#,另一个