UVA 673 - Parentheses Balance （栈）

You are given a string consisting of parentheses () and []. A string of this type is said to be correct:

(a) if it is the empty string

(b) if A and B are correct, AB is correct,

（c) if A is correct, (A) and [A] is correct.

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

Input

The file contains a positive integer n and a sequence of n strings of parentheses ‘()’ and ‘[]’, one string a line.

Output

A sequence of ‘Yes’ or ‘No’ on the output file.

Sample Input

([])

(([()])))

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

Sample Output

Yes

题意：

判断每一个前括号是否都有相匹配的后括号。

思路：

就是栈的使用，碰见前括号了就把他入栈，碰到后括号就在栈尾找是否有相匹配的前括号，如果匹配成功就出栈。

代码：

#include<stdio.h>
#include<string.h>
int main()
{
	int n,i,flag,top,base;
	char a[200],stack[200];
	scanf("%d",&n);
	getchar();
	while(n--)
	{
		top=base=-1;
		flag=0;
		memset(stack,0,sizeof(stack));
		gets(a);
		for(i=0;a[i]!='\0';i++)
		{
			if(a[i]=='('||a[i]=='[')
			{
				stack[++top]=a[i];
			}
			else if(a[i]==')')
			{
				if(stack[top]=='(')
					top--;
				else
				{
					flag=1;
					break;
				}
			}
			else if(a[i]==']')
			{
				if(stack[top]=='[')
					top--;
				else
				{
					flag=1;
					break;
				}
			}
			else
			{
				flag=1;
				break;
			}	
		}
		if(flag==1||top!=base)
			printf("No\n");
		else
			printf("Yes\n");
	}
	return 0;
 }