栈的括号、表达式与递归应用

考点定位

本课深化 栈的括号、表达式与递归应用。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

栈保存尚未完成的上下文。括号匹配、运算符优先级、函数调用都依赖后进先出；发现非法闭括号必须立即失败。

算法推演

中缀转后缀时，操作数直接输出；运算符弹出所有优先级更高或同级左结合的栈顶，再压入当前符号；右括号弹到左括号。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

扫描到任意位置时，栈内只包含尚未匹配的左括号或尚未输出的合法运算符。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：递归改迭代时，必须显式保存返回位置和局部状态。

随课应用

后缀表达式 3 4 + 2 * 7 - 的值是多少？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。