括号配对问题（C语言或JAVA语言代码）

原题链接：题目2 - ACM在线评测系统

描述

现在，有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[", "]", "(", ")" 四种字符

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

样例输入

3
[(])
(])
([[]()])

样例输出

No
No
Yes

解题思路：

由于用栈来实现要复杂得多，这里可以访问“栈”内元素，“栈”顶是右括号而非用栈表示的左括号，括号序列中的字符逐个入“栈”，发现紧挨着“栈顶”的一个元素为']'或')'时，迅速匹配“已配对括号都出栈后”再往前数一个位置的'['或'('。

注意事项：

串长小于10000，注意边界，当所有的括号都匹配以后，“栈顶指针”指向其第一个位置。

参考代码：

C语言描述：

#include <stdio.h>

int main(){
	char s[10001],x[10001];
	int t, a, c;
	scanf("%d", &a);
	while(a--) {
		scanf("%s",s);
		t = c = 0;
		while ( c < 10000 && (x[t++] = s[c++]) != '\0')
			if( t > 1 && (x[t-1] == ']' && x[t-2] == '[' || x[t-1] == ')' && x[t-2] == '(') )
				t -= 2;
		if(t == 1) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

JAVA语言描述：

import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(System.in);
		int a = cin.nextInt();
		while (0 < a--) {
			String s;
			List<String> vec = new ArrayList<String>();
			s = cin.next();
			vec.add(" ");
			for (int i = 0; i < s.length(); i++) {
				vec.add("" + s.charAt(i));
				int b = vec.size();
				if (vec.get(b-1).charAt(0)-1 == vec.get(b-2).charAt(0) || 
				vec.get(b-1).charAt(0)-2 == vec.get(b-2).charAt(0)){
					vec.remove(b-1);
					vec.remove(b-2);
				}
			}
			if (1 == vec.size()) System.out.println("Yes");
			else System.out.println("No");
		}
	}
}