文档介绍：栈栈的应用举例栈与递归的实现队列第三章栈和队列￡数制转换￡栈的应用举例十进制数 N和其他 d进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N = ( N div d ) × d + N mod d (其中: div 为整除运算, mod 为求余运算) 例如: (1348)10 = (2504)8 ,其运算过程如下: N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 由于上述计算过程是从低位到高位顺序产生八进制数的各个数位,而打印输出,一般来说应从高位到低位进行,恰好和计算过程相反。因此,若计算过程中得到八进制数的各位顺序进栈,则按出栈序列打印输出的即为与输入对应的八进制数。算法如下: void conversion ( ) { //对于输入的任意一个非负十进制整数, //打印输出与其等值的八进制数。 InitStack (S); //构造空栈 scanf (“%d ”, N); while (N) { Push (S, N%8); N = N / 8; } while (! StackEmpty(s )) { Pop (S, e); printf (“%d ”, e); } } //conversion ￡括号匹配检验假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即( [ ] ( )) 或[( [ ] [ ]) ] 等为正确的格式, [ ( ] ) 或[ ( ) ) 或( ( ) ] ) 均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如: [ ( [ ] [ ] ) ] 1234 567 8 当计算机接受了第一个括号后,它期待着与其匹配的第八个括号的出现,然而等来的却是第二个括号,此时第一个括号“[”只能暂时靠边,而迫切等待与第二个括号相匹配的、第七个括号”)”的出现,类似的,因等来的是第三个括号“[”, 其期待匹配的程度较第二个括号更急迫,则第二个括号也只能靠边,让位于第三个括号,显然第二个括号的期待急迫性高于第一个括号;在接受了第四个括号之后,第三个括号的期待得到满足,消解之后,第二个括号的期待匹配就成为当前最急迫的任务了, ……,依次类推。可见,这个处理过程恰与栈的特点相吻合。由此,在算法中设置一个栈,每读入一个括号,若是右括号,则或者使置于栈顶的最急迫的期待得以消解,或者是不合法的情况;若是左括号,则作为一个新的更急迫的期待压入栈中,自然使原有的栈中的所有未消解的期待的急迫