学步园

输入

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

输出

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

C语言代码（使用栈）

#include<stdio.h>
typedef struct{
	char st[1000];
	int top;
}Stack;
//初始化
void InitStack(Stack * S)
{
	S -> top = -1;
}
//入栈
int Push(Stack *S,char x)
{
	if(S -> top == 999)return 0;
	S -> top ++;
	S -> st[S -> top] = x;
	return 1;
}
//出栈
int Pop(Stack *S,char *e)
{
	if(S -> top == -1)return 0;
	*e = S -> st[S->top];
	S -> top --;
	return 1;
}
//获取栈顶元素，并用e带出栈顶元素
int GetTop(Stack *S,char *e)
{
	if(S -> top == -1)return 0;
	*e = S -> st[S -> top];
	return 1;
}
//判断栈是否为空
int IsEmpty(Stack *S)
{
	if(S -> top == -1)
		return 1;//返回1说明栈为空
	return 0;
}
//检查是否配对
int IsMath(char e,char str)
{
	if((e =='(' && str == ')') || (e =='[' && str == ']'))
		return 1;//返回1说明配对
	return 0;
}
void Math(char str[],Stack *s)
{
	char e;
	for(int i = 0; str[i] !='\0';i ++){
		//printf("str[%d] = %c\n",i,str[i]);
		switch(str[i]){
			//左括号均进栈
		case '(':
		case '[':Push(s,str[i]);break;
			//右括号进行下一步判断
		case ']':
		case ')':
			if(IsEmpty(s)){//如果栈为空，说明当前的右括号没有与之配对的左括号
				printf("No\n");
				return ;
			}
			else
			{
				GetTop(s,&e);//找到栈顶元素
				//printf("e = %c\n",e);
				
				if(IsMath(e,str[i]))//判断栈顶元素是否与当前str[i]配对
					Pop(s,&e);//如果配对，将栈顶元素退栈
				else{//如果不配对，则判断该字符串不配对
					printf("No\n");
					return;
				}
			}
		}//switch
	}//for
	//当for循环结束后，判断栈是否为空，如果为空，说明栈内存在不配对的括号，则判断该字符串不配对
	if(IsEmpty(s))
		printf("Yes\n");
	else
		printf("No\n");
}
int main()
{
	int N;
	Stack s;
	char str[10010];
	scanf("%d",&N);
	getchar();//消除回车
	while(N --){
		InitStack(&s);//初始化栈
		scanf("%s",str);
		Math(str,&s);
		//printf("str = %s\n",str);//测试内容，查看输入的串
	}//while
	return 0;
}

下面提供数组代替栈进行操作，

#include<stdio.h>
int main()
{
    int n;
	char s[10005];//存储原字符串
	char stick[10005];//代替栈的数组
	scanf("%d",&n);
	while(n--)
	{
		int i,flag=1;//flag 用于标记该串是否配对，为1说明配对，为0说明不配对
		int top=-1;//代替栈顶标记top;
		scanf("%s",s);
		for(i=0;s[i]!='\0';i++)//对s中的每一个字符逐一判断
		{
			if(s[i]=='['||s[i]=='(')//如果为左括号，直接复制到stick数组中，相当于进栈
			{
				top++;//标记数组stick当前位置
				stick[top]=s[i];
			}
			else
			{//    “栈”不为空     检查stick中的stick[top]是否和当前s[i]相等
				if((top>=0)&&((s[i]==']'&&stick[top]=='[')||(s[i]==')'&&stick[top]=='(')))
					top--;//“退栈”
				else//若为“栈”空，或者当前字符不配对，说明该串不配对
				{
					flag=0;break;
				}
			}
		}
		if(flag==1)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

注： 以下条件的理解

if((top>=0)&&((s[i]==']'&&stick[top]=='[')||(s[i]==')'&&stick[top]=='(')))

top保存了在该次for循环中对应上次”进栈“时”栈顶“的位置，相当于 用栈实现时的 ”得到栈顶元素并判断当前str[i]是否与栈顶元素相等“；