数据结构括号排序.ppt

总 结 括号匹配处理中，将左括号依次存入数组，每次存进去的左括号都是在数组的最上部，一旦遇到左右括号匹配，将数组最上部的左括号移走； 将存入数组的左括号视为线性表，上述的存入与移走对应线性表的插入和删除； 与第二章讲述的线性表的插入与删除的唯一区别在于这种插入与删除只能在线性表的表尾做。 计算表达式括号匹配问题 假定表达式中只包含两种括号[ ]、（），例如表达式：A×[ (B－C) + (D－E) ] / (F + G) A×[ (B－C) + (D－E) ] / (F + G) 解题思路： 借助于数组顺序处理表达式中的每个括号，遇到左括号依次存入数组，遇到右括号，则与数组最上部的左括号匹配，如果发现括号匹配错误，则终止检测过程。如果匹配成功，则将顶部的左括号移走。继续往下…,一直到最后一个括号 pos = -1 2 1 0 A×[ (B－C) + (D－E) ] / (F + G) pos = -1 2 1 0 2 1 0 [ pos = 0 A×[ (B－C) + (D－E) ] / (F + G) pos = 0 2 1 0 pos = 1 [ ( A×[ (B－C) + (D－E) ] / (F + G) pos = 0 2 1 0 pos = 1 [ ( A×[ (B－C) + (D－E) ] / (F + G) pos = 0 2 1 0 pos = 1 [ ( A×[ (B－C) + (D－E) ] / (F + G) pos = 0 2 1 0 pos = 1 [ ( A×[ (B－C) + (D－E) ] / (F + G) pos = -1 2 1 0 pos = 0 [ A×[ (B－C) + (D－E) ] / (F + G) pos = 0 2 1 0 pos = -1 ( A×[ (B－C) + (D－E) ] / (F + G) pos = -1 3 2 1 pos = 0 (