網站如何做sem優(yōu)化seo搜索引擎優(yōu)化工程師招聘
目錄
一、棧的括號匹配
二、代碼實現(xiàn)
1.方法創(chuàng)建
2.數(shù)據(jù)測試
3.完整的程序代碼
總結
一、棧的括號匹配
要完成今天的任務，需要先來了解一下什么是棧的括號匹配。首先，顧名思義，括號匹配就是指將一對括號匹配起來，我們給定一個字符串（字符串中除了各類括號，也可以有別的字符），將字符串中的所有括號都根據(jù)規(guī)則：對應的一對左括號與右括號按“先左后右”的順序匹配起來，這個過程即為括號匹配。
在判斷括號匹配時，需要注意一些細節(jié)：
- 必須是對應的一對左括號與右括號，即“（ ”與“ ）”對應，“ [ ”與“ ] ”對應，“ { ”與“ } ”對應。
- 必須是“一左一右”，不能兩個均為左括號或者兩個均為右括號，即“（ ”與“ ）”可以匹配，但是“（ ”與“（ ”不匹配，“ ）”與“ ）”也不匹配。
- 必須按“先左后右”的順序，即“（? ）”匹配，但是“ ）（ ”就不匹配。
- 括號匹配遵循就近原則，以當前括號的左邊第一個括號為準。比如在下面的字符串中，設第6個括號為當前括號，那么就以該括號左邊第一個括號為準，即以第5個括號為準，所以5、6成功匹配。可以看到，在下圖中第6個括號與第3個括號也滿足了以上三個基本條件，但是因為就近原則的存在，所以3、6不匹配。同理，如果第5個括號改為了“ [ ”或者“ { ”，那么5、6也不會匹配。
- 括號匹配遵循匹配消除原則，一旦某一對括號匹配成功，那么該對括號就“消除”，繼續(xù)匹配后面的括號。比如在上圖中，5、6成功匹配后“消除”，然后4、7繼續(xù)匹配，再比如“ { [ ( ) ] } ”也是匹配的。
- 所給字符串中的全部括號都匹配成功才算完成了括號匹配，比如“ [ { ( [ ( ) ] ) } ] ”是匹配的，但是“ ( [ { ( [ ] ) ] ] ) ”就不匹配。
- 在所給的字符串中，除了各類括號，也可以有別的字符，比如“ 10 / { [ 4 - ( 5 - 2 ) ] * 2 } ”也是匹配的。
二、代碼實現(xiàn)
弄清楚基本概念后，就可以進行代碼實現(xiàn)了。根據(jù)“先左后右”的順序要求以及匹配消除原則，我們可以按如下步驟進行括號匹配（因為別的非括號字符對于括號匹配不起任何作用，所以直接視為透明就行）：
- 遇到左括號“（ ”、“ [ ”、“ { ”就直接入棧，在棧中存放
- 遇到右括號“ ）”、“ ] ”、“ } ”就從棧中彈出棧頂元素，與該右括號進行匹配，如果二者匹配成功就“消除”，繼續(xù)匹配后面的括號；如果二者匹配不成功，直接輸出不匹配即可
不過，需要注意一點，由于要求的是字符串中的全部括號均匹配才算成功，所以如果匹配完畢后發(fā)現(xiàn)棧中仍然還存在左括號或者棧不空，那么也算作匹配失敗。
對于這個問題，我們當然可以選擇在匹配完畢后直接判斷棧是否為空，但是我們也可以采取另一種方式：即在進行括號匹配之前，入棧一個非括號字符作為棧底元素，再在匹配完畢后進行出棧操作，判斷此時出棧的元素是否為該非括號字符，如果是，則說明字符串中的全部括號均已匹配；如果不是，則直接返回不匹配。
1.方法創(chuàng)建
進行代碼模擬時，我們只需要在昨天的代碼基礎上增加一個括號匹配的方法即可，如下：
/************************ 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類型的參數(shù)paraString即為要輸入的字符串，再創(chuàng)建一個棧，并入棧一個'#'，將'#'?作為棧底的非括號字符。
然后，利用charAt()方法+for循環(huán)，將字符串中的字符一個一個讀取出來。
補充：
length()方法：作用是返回字符串的長度，調用格式為字符串名.length()
charAt()方法：作用是獲取字符串中指定索引值的字符，調用格式為字符串名.charAt(指定索引值)
根據(jù)之前的分析，這里需要進行讀取字符的判斷，且判斷分支較多，符合switch語句適用的情況（單一變量的多個不同取值問題），所以我們采用了switch語句。
匹配完畢后，進行出棧操作，并判斷此時出棧的元素是否為'#'，如果不是則直接返回false；如果是，則返回true。
2.數(shù)據(jù)測試
下面我們進行數(shù)據(jù)測試，這里用到了以下五個數(shù)據(jù)：
- [ 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 main3.完整的程序代碼
package datastructure;/***Char stack. I do not use Stack because it is already defined in Java.**@auther Xin Lin 3101540094@qq.com.*/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運行結果：
可以發(fā)現(xiàn)運行結果與我們之前的預測是完全相同的。?
總結
總體來說，今天學習的內容不是很復雜，簡單來說就是對昨天棧的入棧出棧等操作進行一個應用，而且根據(jù)今天代碼的難度，其實可以知道括號匹配算是棧的一個基本應用，不過它也是一個非常重要的應用，在今后很多算法和問題中都會涉及到。