例:括号匹配问题 如{[(3+5)×2]-7}÷3是合法的表达式, [(3+5]×2)-7或者(3+5)×2]-7)÷3非法 规则:从左向右,第一个出现的右括号需要和最后 个出现的左括号配对,“后进先出” 算法4.12 初始化栈 从左向右读入表达式中的括号 如果是左括号,进栈 如果是右括号,检查栈顶的左括号是否与它配对,若配对则左括 号出栈,否则错误 读入结束后,栈应该是空的,否则错误 思考:如何对算法进行改进,进一步检查括号的优 先级?即:[]中不能有{},()中不能有[]和{} 2021/1/29 数据结构及其算法第4章栈和队列•例：括号匹配问题 •如{[(3+5)×2]-7}÷3是合法的表达式， [(3+5]×2)-7或者((3+5)×2]-7)÷3非法 •规则：从左向右，第一个出现的右括号需要和最后 一个出现的左括号配对，“后进先出” •算法4.12 • 初始化栈 • 从左向右读入表达式中的括号 • 如果是左括号，进栈 • 如果是右括号，检查栈顶的左括号是否与它配对，若配对则左括 号出栈，否则错误 • 读入结束后，栈应该是空的，否则错误 •思考：如何对算法进行改进，进一步检查括号的优 先级？即：[]中不能有{}，()中不能有[]和{} 2021/1/29 数据结构及其算法 第4章 栈和队列 11