資料結構的應用——使用棧實作字元串括号比對檢查

假設表達式中允許包含兩種括号：圓括号和方括号，其嵌套順序随意，及([]())或[([][])]等均為正确的格式，[(])或([())或(()]均為不正确的格式。

比對算法的思想是：

首先将第一個括号壓入棧，然後從第二個括号開始，如果與棧頂元素能比對，能将棧頂元素彈出；如果不比對，則将該元素壓入棧中。

當帶比對字元串周遊結束後，檢查棧是否為空，為空則表示比對成功了，如果非空則表示還有括号未能比對，即該字元串比對失敗。

具體代碼：

package ds.linerlist;

import java.util.Stack;

/**

* 使用棧實作字元串的括号比對檢查。

* @author <a href="mailto:[email protected]" target="_blank" rel="external nofollow" target="_blank" rel="external nofollow" mce_href="mailto:[email protected]" target="_blank" rel="external nofollow" target="_blank" rel="external nofollow" >Bao Yiming</a>

*/

public class BracketMatch {

/**

* 進行比對的算法。

* @param str 待檢查的字元串。

* @return

*/

public static boolean match(String str) {

Stack stack = new Stack(); // 定義一個存放括号的棧。

char[] ca = str.toCharArray(); // 将字元串轉為字元數組以便對其周遊。

stack.push((Character) ca[0]); // 首先将第一個字元壓入棧中。

/*

* 從第二個字元開始，依次與棧中字元比對。

* 成功則将棧頂元素彈出。

* 失敗則将字元數組中的目前字元壓入棧中。

*/

for (int index = 1; index < ca.length; ++index) {

Character c1 = (Character) stack.peek();

Character c2 = ca[index];

if ((c1.equals('(') && c2.equals(')'))

|| (c1.equals('[') && c2.equals(']'))) {

stack.pop();

} else {

stack.push(c2);

}

}

return stack.empty();

}

}