ds3.2陆小马功钟浩.pptVIP

§3.2 栈的应用举例 栈的应用 例1：数制转换 “除基取余法” 除基数取余数，逆序排列。 (1348)10 = (2504)8 简单的数制转换算法 //将正整数n转换为r进制数输出 void conversion ( int n, int r ) { InitStack(S); do { Push(S, n%r); n = n/r; } while ( n!=0 ); while ( ! StackEmpty(S) ) { Pop(S,e); print(e); } } 例2：括号匹配 括号匹配问题 括号匹配 {[( )]}，(( ){ })，( ) 括号不匹配 (( )，( )]，([ )] 检查括号匹配的算法 设一栈 遇到左括号则入栈， 遇到右括号时，若栈空，则不匹配(右括号太多)，否则，如果栈顶元素与该右括号匹配，则出栈，否则不匹配(括号不配对)。 输入结束后，若栈为空，则匹配，否则不匹配(左括号太多)。 检查括号匹配的算法 //检查括号匹配的算法 bool match ( ) { InistStack(S); read(c); while ( c!=EOF ) { switch(c) { case (‘, [‘, {: Push(S,c); break; case )‘, ]‘, }: if(StackEmpty(S)) return false; Pop(S,e); if(c==) e!=() return false; if(c==] e!=[) return false; if(c==} e!={) return false; break; } read(c); //读下一个字符 } if( StackEmpty(S) ) return true; else return false; } 例3：计算后缀表达式 后缀表达式 中缀表达式 a @ b 后缀表达式 a b @ 分析 中缀表达式1+2*3+(4*5+6)*7 根据运算符的优先级进行计算 后缀表达式123*+45*6+7*+ 按照运算符的顺序计算，不需要括号 算法 设一栈存放操作数 遇到运算符，则取出栈顶的两个数进行运算，将结果入栈 最终结果保存在栈中。 计算后缀表达式的算法 //计算后缀表达式 int Postfix ( ) { InitStack(S); read(c); while ( c!== ) { if( isdigit(c) ) { read(v); Push(S,v); } else { Pop(S,b); Pop(S,a); Push(S, Operate(a,c,b)); } read(c); } Pop(S,result); return result; } 例4：计算中缀表达式 分别设操作数栈和运算符栈。 若读入操作数则进栈。 如果读入运算符，则与栈顶运算符比较，若优先级高于栈顶运算符，则入栈；否则，不断弹出栈顶运算符和两个操作数并执行计算，直到栈顶运算符优先级更低。 P53 例5：中缀表达式转化为后缀表达式 分析 中缀表达式1+2*3+(4*5+6)*7 后缀表达式123*+45*6+7*+ 算法 读到操作数时立即输出 操作符存放在栈中，遇到操作符时，从栈中弹出操作符直到遇到优先级更低的运算符为止。 * * 2 0 2 5 2 21 0 21 168 4 168 1348 N mod 8 N / 8 N