数据结构【DS】栈的应用

描述一下如何实现括号匹配？

初始时栈为空。

从左往右遍历算术表达式中的每个括号元素：

①当遍历到左括号时，将其压入栈顶。

②当遍历到右括号时，将栈顶元素出栈，并判断出栈的左括号与当前遍历的右括号是否匹配（左小括号应与右小括号匹配、左中括号应与右中括号匹配）：

如果不匹配，则算法结束，括号匹配失败；

如果匹配，则继续遍历下一个括号元素。

当遍历完算术表达式中所有括号元素后，若栈为空，则括号匹配成功；若栈非空，则括号匹配失败。

如何用栈实现中缀转后缀？【分机算和手算】

机算：

从左向右开始扫描中缀表达式:

遇到数字时，加入后缀表达式;

遇到运算符时:

a.若为'('，入栈;

b.若为')'，则依次把栈中的运算符加入后缀表达式，直到出现' (',从栈中删除' (';

c.若为除括号外的其他运算符，当其优先级高于除' ('外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或遇到了一个左括号为止。”

当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。

手算：

把运算符号移动到对应的括号后面

如何用后缀表达式进行求值？

• 利用后缀表达式，每遇到操作数入栈，操作符时出栈两个操作数，运算后入栈。

在递归调用时，系统需要存储什么数据？

• 在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储

 

在递归调用时，先调用的函数是靠近栈底还是栈顶？

• 越靠后被调用的函数信息越靠近栈顶
• 先调用的函数靠近栈底

 

递归的次数过多会造成什么？

• 递归次数过多容易造成栈溢出

 

某个函数return后该函数在栈中的信息怎么处理？

• 某个函数return后该函数在栈中的信息就会消失