栈的应用

二、栈的应用
栈是一个重要的数据结构，其特性简而言之就是“后进先出”，这种特性在计算机中有着广泛的运用。其实程序员无时无刻不在使用者栈，函数的调用是我们间接使用栈的最好的例子，但是栈在实际中的运用远不止这些，比较经典的应用还包括括号匹配、逆波兰表达式的求值等，下面就介绍这两个对栈的简单应用：

1、括号匹配问题
1）括号匹配问题的四种结果： 
（1）左右括号匹配正确 
（2）左右括号匹配错误 
（3）左括号多于右括号 
（4）右括号多于左括号 
2）算法基本思想 
（1）顺序扫描算数表达式（表现为一个字符串），当遇到三种类型的左括号时候让该括号进栈； 
（2）当扫描到某一种类型的右括号时，比较当前栈顶元素是否与之匹配，若匹配，退栈继续判断；若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确； 
（3）若字符串当前为某种类型的右括号而堆栈已经空，则右括号多于左括号； 
（4）字符串循环扫描结束时，若堆栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号； 
（5）否则，括号配对正确。 
 

文章来源: blog.csdn.net，作者：网奇，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jacke121/article/details/100170004