日撸Java三百行（day15：栈的应用之括号匹配）

目录

一、栈的括号匹配

二、代码实现

1.方法创建

2.数据测试

3.完整的程序代码

总结

---

一、栈的括号匹配

要完成今天的任务，需要先来了解一下什么是栈的括号匹配。首先，顾名思义，括号匹配就是指将一对括号匹配起来，我们给定一个字符串（字符串中除了各类括号，也可以有别的字符），将字符串中的所有括号都根据规则：对应的一对左括号与右括号按“先左后右”的顺序匹配起来，这个过程即为括号匹配。

在判断括号匹配时，需要注意一些细节：

• 必须是对应的一对左括号与右括号，即“（ ”与“ ）”对应，“ [ ”与“ ] ”对应，“ { ”与“ } ”对应。
• 必须是“一左一右”，不能两个均为左括号或者两个均为右括号，即“（ ”与“ ）”可以匹配，但是“（ ”与“（ ”不匹配，“ ）”与“ ）”也不匹配。
• 必须按“先左后右”的顺序，即“（  ）”匹配，但是“ ）（ ”就不匹配。
• 括号匹配遵循就近原则，以当前括号的左边第一个括号为准。比如在下面的字符串中，设第6个括号为当前括号，那么就以该括号左边第一个括号为准，即以第5个括号为准，所以5、6成功匹配。可以看到，在下图中第6个括号与第3个括号也满足了以上三个基本条件，但是因为就近原则的存在，所以3、6不匹配。同理，如果第5个括号改为了“ [ ”或者“ { ”，那么5、6也不会匹配。

• 括号匹配遵循匹配消除原则，一旦某一对括号匹配成功，那么该对括号就“消除”，继续匹配后面的括号。比如在上图中，5、6成功匹配后“消除”，然后4、7继续匹配，再比如“ { [ ( ) ] } ”也是匹配的。
• 所给字符串中的全部括号都匹配成功才算完成了括号匹配，比如“ [ { ( [ ( ) ] ) } ] ”是匹配的，但是“ ( [ { ( [ ] ) ] ] ) ”就不匹配。
• 在所给的字符串中，除了各类括号，也可以有别的字符，比如“ 10 / { [ 4 - ( 5 - 2 ) ] * 2 } ”也是匹配的。

二、代码实现

弄清楚基本概念后，就可以进行代码实现了。根据“先左后右”的顺序要求以及匹配消除原则，我们可以按如下步骤进行括号匹配（因为别的非括号字符对于括号匹配不起任何作用，所以直接视为透明就行）：

• 遇到左括号“（ ”、“ [ ”、“ { ”就直接入栈，在栈中存放
• 遇到右括号“ ）”、“ ] ”、“ } ”就从栈中弹出栈顶元素，与该右括号进行匹配，如果二者匹配成功就“消除”，继续匹配后面的括号；如果二者匹配不成功，直接输出不匹配即可

不过，需要注意一点，由于要求的是字符串中的全部括号均匹配才算成功，所以如果匹配完毕后发现栈中仍然还存在左括号或者栈不空，那么也算作匹配失败。

对于这个问题，我们当然可以选择在匹配完毕后直接判断栈是否为空，但是我们也可以采取另一种方式：即在进行括号匹配之前，入栈一个非括号字符作为栈底元素，再在匹配完毕后进行出栈操作，判断此时出栈的元素是否为该非括号字符，如果是，则说明字符串中的全部括号均已匹配；如果不是，则直接返回不匹配。

1.方法创建

进行代码模拟时，我们只需要在昨天的代码基础上增加一个括号匹配的方法即可，如下：

    /************************ Is the bracket matching?* * @param paraString The given expression.* @return Match or not.**********************/public static boolean bracketMatching(String paraString) {// Step 1. Initialize the stack through pushing a '#' at the bottom.CharStack tempStack = new CharStack();tempStack.push('#');char tempChar, tempPoppedChar;// Step 2. Process the string. For a string, length() is a method// instead of a member variable.for(int i = 0; i < paraString.length(); i++) {tempChar = paraString.charAt(i);switch(tempChar) {case '(':case '[':case '{':tempStack.push(tempChar);break;case ')':tempPoppedChar = tempStack.pop();if(tempPoppedChar != '(') {return false;} // of ifbreak;case ']':tempPoppedChar = tempStack.pop();if(tempPoppedChar != '[') {return false;} // of ifbreak;case '}':tempPoppedChar = tempStack.pop();if(tempPoppedChar != '{') {return false;} // of ifbreak;default:// Do nothing} // of switch} // of for itempPoppedChar = tempStack.pop();if(tempPoppedChar != '#') {return false;} // of ifreturn true;} // of bracketMatching

首先，定义括号匹配的方法bracketMatching，其中String类型的参数paraString即为要输入的字符串，再创建一个栈，并入栈一个'#'，将'#' 作为栈底的非括号字符。

然后，利用charAt()方法+for循环，将字符串中的字符一个一个读取出来。

补充：

length()方法：作用是返回字符串的长度，调用格式为字符串名.length()

charAt()方法：作用是获取字符串中指定索引值的字符，调用格式为字符串名.charAt(指定索引值)

根据之前的分析，这里需要进行读取字符的判断，且判断分支较多，符合switch语句适用的情况（单一变量的多个不同取值问题），所以我们采用了switch语句。

匹配完毕后，进行出栈操作，并判断此时出栈的元素是否为'#'，如果不是则直接返回false；如果是，则返回true。

2.数据测试

下面我们进行数据测试，这里用到了以下五个数据：

• [ 2 + (1 - 3) ] * 4
• (  )   )
• ( ) ( ) ( ( ) )
• ( { } [ ] )
• ) (

显然，通过直接思考可以预测第1、3、4个字符串是匹配的，剩下的是不匹配的。

    /************************The entrance of the program.** @param args Not used now.**********************/public static void main(String[] args) {CharStack tempStack = new CharStack();for(char ch = 'a'; ch < 'm'; ch++) {tempStack.push(ch);System.out.println("The current stack is: " + tempStack);} // of for chchar tempChar;for(int i = 0; i < 12; i++) {tempChar = tempStack.pop();System.out.println("Popped: " + tempChar);System.out.println("The current stack is: " + tempStack);} // of for iboolean tempMatch;String tempExpression = "[2 + (1 - 3)] * 4";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);tempExpression = "( )  )";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);tempExpression = "()()(())";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);tempExpression = "({}[])";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);tempExpression = ")(";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);} // of main

3.完整的程序代码

package datastructure;/***Char stack. I do not use Stack because it is already defined in Java.**@auther Xin Lin [e-mail].*/public class CharStack {/*** The depth.*/public static final int MAX_DEPTH = 10;/*** The actual depth.*/int depth;/*** The data.*/char[] data;/************************ Construct an empty char stack.**********************/public CharStack() {depth = 0;data = new char[MAX_DEPTH];} // of the first constructor/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString = "";for (int i = 0; i < depth; i++) {resultString += data[i];} // of for ireturn resultString;} // of toString/************************ Push an element.* * @param paraChar The given char.* @return Success or not.**********************/public boolean push(char paraChar) {if (depth == MAX_DEPTH) {System.out.println("Stack full.");return false;} // of ifdata[depth] = paraChar;depth++;return true;} // of push/************************ Pop an element.* * @return The popped char.**********************/public char pop() {if(depth == 0) {System.out.println("Nothing to pop.");return '\0';} // of ifchar resultChar = data[depth - 1];depth--;return resultChar;} // of pop/************************ Is the bracket matching?* * @param paraString The given expression.* @return Match or not.**********************/public static boolean bracketMatching(String paraString) {// Step 1. Initialize the stack through pushing a '#' at the bottom.CharStack tempStack = new CharStack();tempStack.push('#');char tempChar, tempPoppedChar;// Step 2. Process the string. For a string, length() is a method// instead of a member variable.for(int i = 0; i < paraString.length(); i++) {tempChar = paraString.charAt(i);switch(tempChar) {case '(':case '[':case '{':tempStack.push(tempChar);break;case ')':tempPoppedChar = tempStack.pop();if(tempPoppedChar != '(') {return false;} // of ifbreak;case ']':tempPoppedChar = tempStack.pop();if(tempPoppedChar != '[') {return false;} // of ifbreak;case '}':tempPoppedChar = tempStack.pop();if(tempPoppedChar != '{') {return false;} // of ifbreak;default:// Do nothing} // of switch} // of for itempPoppedChar = tempStack.pop();if(tempPoppedChar != '#') {return false;} // of ifreturn true;} // of bracketMatching/************************The entrance of the program.** @param args Not used now.**********************/public static void main(String[] args) {CharStack tempStack = new CharStack();for(char ch = 'a'; ch < 'm'; ch++) {tempStack.push(ch);System.out.println("The current stack is: " + tempStack);} // of for chchar tempChar;for(int i = 0; i < 12; i++) {tempChar = tempStack.pop();System.out.println("Popped: " + tempChar);System.out.println("The current stack is: " + tempStack);} // of for iboolean tempMatch;String tempExpression = "[2 + (1 - 3)] * 4";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);tempExpression = "( )  )";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);tempExpression = "()()(())";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);tempExpression = "({}[])";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);tempExpression = ")(";tempMatch = bracketMatching(tempExpression);System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);} // of main
} // of class CharStack

运行结果：

可以发现运行结果与我们之前的预测是完全相同的。 

总结

总体来说，今天学习的内容不是很复杂，简单来说就是对昨天栈的入栈出栈等操作进行一个应用，而且根据今天代码的难度，其实可以知道括号匹配算是栈的一个基本应用，不过它也是一个非常重要的应用，在今后很多算法和问题中都会涉及到。