栈的应用之判断括号匹配

1，括号匹配是指在某个字符串中，左括号出现的顺序及个数与右括号保持一致。如：

{ [ ( ) ] } ----匹配 { [ ] } ----匹配 { ( } ) ---不匹配①

{ [ ( ) ] -----不匹配② { [ ] } ) ----不匹配③

不匹配一共有如上三种情况：①左右对应的括号不匹配，②右括号比左括号个数多，①右括号比左括号个数少

2，使用栈来判断括号匹配的思路：

首先 new 一个栈的实例用来保存表达式中的左括号。

然后，根据 index 指针依次扫描表达式各个字符，遇到左括号类的字符 char 则将之入栈，遇到右括号类的字符则将栈顶的左括号字符出栈并且与 char 进行比较，看是否匹配。比较功能由 isPaired(char left, char right)函数实现。

为什么 isBalanced 初始化成true 并将之放到for 循环中？

这样，只要在括号比较中有不匹配的括号( isBalaced 会被设置成 false)，for 循环就不再需要执行了，即不再需要判断表达式中后面的括号是否匹配了。

3，括号匹配的JAVA代码实现

判断括号匹配时，需要一个栈来保存表达式中的左括号，顺序栈 SequenceStack.java 的实现参考：

 1 import list.SequenceStack;
 2 
 3 public class BalanceChecker {
 4     /*
 5      * @Task:使用栈判断表达式的括号匹配
 6      * @param: expression 待检查的字符串
 7      * @return 若括号匹配则返回true
 8      */
 9     public static boolean checkBalance(String expression){
10         SequenceStack<Character> openDelimiterStack = new SequenceStack<Character>();
11         int characterCount = expression.length();
12         boolean isBalanced = true;
13         int index = 0;//标记是否已经到达表达式末尾
14         char nextCharacter = ' ';//标记表达式中下一个待判断的字符
15         for(; isBalanced && (index < characterCount); index++){
16             nextCharacter = expression.charAt(index);
17             switch(nextCharacter){//只对表达式中的括号进行处理,其他字符都不满足switch中的case
18             case '(': case '[': case '{':
19                 openDelimiterStack.push(nextCharacter);//只有表达式中的左括号才能入栈
20                 break;
21             case ')': case ']': case '}':
22                 if(openDelimiterStack.empty())
23                     isBalanced = false;//当碰到右括号时,此时表达式还未结束,但栈中已经没有左括号了,说明右括号多于左括号
24                 else{//栈中还有左括号
25                     char openDelimiter = openDelimiterStack.pop();
26                     isBalanced = isPaired(openDelimiter, nextCharacter);//判断此时栈中左括号与表达式字符右括号是否匹配
27                 }
28                 break;
29             default: break;//对于 非括号字符直接执行  break;
30             }//end switch
31         }//end for
32         
33         //表达式中的右括号已经判断完了,但还有左括号(栈未空),说明左括号个数多于右括号
34         if(!openDelimiterStack.empty())
35             isBalanced = false;
36         return isBalanced;
37     }
38     //判断左右括号是否匹配
39     private static boolean isPaired(char left, char right){
40         return (left == '(' && right == ')') || 
41                 (left == '[' && right == ']') ||
42                 (left == '{' && right == '}');
43     }
44     
45     //for test purpose
46     public static void main(String[] args) {
47         String expression = "a {b [c (d + e)/2 - f] + 1}";
48         boolean isBalanced = checkBalance(expression);
49         if(isBalanced)
50             System.out.println(expression + " is Balanced!");
51         else
52             System.out.println(expression + " is not Balanced!");
53     }
54 }

算法详细解释参考《数据结构与算法JAVA语言描述第二版》--Frank M.Carrano 著.第21章