数据结构的应用——使用栈实现字符串括号匹配检查

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套顺序随意，及([]())或[([][])]等均为正确的格式，[(])或([())或(()]均为不正确的格式。

匹配算法的思想是：

首先将第一个括号压入栈，然后从第二个括号开始，如果与栈顶元素能匹配，能将栈顶元素弹出；如果不匹配，则将该元素压入栈中。

当带匹配字符串遍历结束后，检查栈是否为空，为空则表示匹配成功了，如果非空则表示还有括号未能匹配，即该字符串匹配失败。

具体代码：

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();

}

}