本文共 2823 字，大约阅读时间需要 9 分钟。
1，括号匹配是指在某个字符串中，左括号出现的顺序及个数与右括号保持一致。如：
{ [ ( ) ] } ----匹配 { [ ] } ----匹配 { ( } ) ---不匹配①
{ [ ( ) ] -----不匹配② { [ ] } ) ----不匹配③
不匹配一共有如上三种情况：①左右对应的括号不匹配，②右括号比左括号个数多，①右括号比左括号个数少
2，使用栈来判断括号匹配的思路：
首先 new 一个栈的实例用来保存表达式中的左括号。
然后，根据 index 指针 依次扫描表达式各个字符，遇到左括号类的字符 char 则将之入栈，遇到右括号类的字符则将栈顶的左括号字符出栈并且与 char 进行比较，看是否匹配。比较功能由 isPaired(char left, char right)函数实现。
为什么 isBalanced 初始化成true 并将之放到for 循环中？
这样，只要在括号比较中有不匹配的括号( isBalaced 会被设置成 false)，for 循环就不再需要执行了，即不再需要判断表达式中后面的括号是否匹配了。
3，括号匹配的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 openDelimiterStack = new SequenceStack ();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中的case18 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 switch31 }//end for32 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 purpose46 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 else52 System.out.println(expression + " is not Balanced!");53 }54 }
算法详细解释参考《数据结构与算法JAVA语言描述第二版》--Frank M.Carrano 著.第21章
本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/，如需转载请自行联系原作者