NYOJ 2 括号配对问题

￡神魔★判官ぃ 2022-09-19 04:30 177阅读 0赞

## 括号配对问题 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

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

输入

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

输出

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

样例输入

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

样例输出

No
    No
    Yes

/*括号匹配，利用顺序栈来做，这样简单易处理*/
    
    #include <stdio.h>
    
    int main()
    {
    	int n, top, j;
    	char str[10010],stack[5050];//数组开大一点，防止溢出，栈开一半
    	scanf("%d",&n);
    	while (n--)
    	{
    		scanf("%s",str);
    		if (str[0] == ')' || str[0] == ']')
    		{//如果第一个字符就失配，stack[0]作标志
    			stack[0] = '1';
    		}
    		else
    		{
    			for (top = 0,j=0; str[j] != '\0';j++)
    			{
    				if (str[j] == '(' || str[j] == '[')
    				{//如果是(和[，则进栈，栈指针上移
    					stack[top++] = str[j];
    				}
    				else if (str[j] == ']')
    				{//如果当前字符是]，栈顶元素是[，则匹配，[出栈，指针下移。
    					if (stack[top-1] != '[')
    					{
    						stack[0] = '1';
    						break;
    					}
    					else
    					{
    						stack[--top] = '0';
    					}
    				}
    				else 
    				{//如果当前字符是)，栈顶元素是(，则匹配，(出栈，指针下移。
    					if (stack[top-1] != '(')
    					{
    						stack[0] = '1';
    						break;
    					}
    					else
    					{
    						stack[--top] = '0';
    					}
    				}
    			}
    		}
    		printf(stack[0] == '0'?"Yes\n":"No\n");
    		
    	}
    	return 0;
    }