//http://acm.nyist.net/JudgeOnline/problem.php?pid=2
括号配对问题
时间限制：3000 ms | 内存限制：65535 KB
难度：3
描述
现在，有一行括号序列，请你检查这行括号是否配对。
输入
第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符
输出
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No
样例输入
3
[(])
(])
([[]()])样例输出
No
No
Yes来源
网络
上传者
naonao
import java.util.*;
public class 括号匹配2_2013_5_23 {//
public static void main(String[] args) {
//Bracket B=new Bracket();
Scanner input = new Scanner(System.in);
int n = input.nextInt();
while (n-- > 0) {
String a = input.next();
if (Bracket.isMatch(a))
System.out.println("Yes");
else
System.out.println("No");
}
}
public static class Bracket{
static boolean isMatch(String b){
boolean m = true;
Stack<Character> st = new Stack<Character>();
for (int i = 0; i < b.length(); i++) {
char p = b.charAt(i);
if (p == '[' || p == '(')
st.push(p);
if (p == ']' || p == ')') {
if (st.isEmpty()) {
m = false;
break;
}
else {
if ((p == ']' && st.peek() == '[')
|| (p == ')' && st.peek() == '('))
st.pop();
else {
m = false;
break;
}
}
}
}
if(!st.isEmpty())m=false;
return m;
}
}
}
/*//BufferedReader读取字符速度更快
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Stack;
public class 括号匹配2013_5_23 {
public static void main(String[] args) {//==========效率更高===========，
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = null;
Stack<Character> stack = new Stack<Character>();
try{
int cases = Integer.valueOf(br.readLine());
while(cases-->0){
str = br.readLine();
int strLength = str.length();
boolean isMatch = true;
stack.clear();
stack.push('#');
for(int i = 0; i < strLength; ++i){
char ch = str.charAt(i);
switch(ch){
case '(':
stack.push(ch);
break;
case '[':
stack.push(ch);
break;
case ')':
if(stack.pop() != '('){
isMatch = false;
}
break;
case ']':
if(stack.pop() != '['){
isMatch = false;
}
break;
default:
isMatch = false;
break;
}
if(!isMatch){
break;
}
}
if(isMatch&&stack.pop()=='#'){
System.out.println("Yes");
}else{
System.out.println("No");
}
}
}catch(Exception e){
e.printStackTrace();
}
}
}
*/
作者：chao1983210400 发表于2013-7-10 13:49:50