UVA 673 - Parentheses Balance

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

1. if it is the empty string
2. if A and B are correct, AB is correct,
3. 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

3 ([])

(([()])))

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

Sample Output

Yes No Yes

括号比對算法

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int main()
{
	int n;
	scanf ("%d",&n);
	getchar();
	while (n--)
	{
		bool flag=true;
		stack <char> s;
		while (!s.empty())
			s.pop();
		char a[1000]={0};
		gets(a);
		int l=strlen(a);
		//Ñ­»·Ìõ¼þ²»ÒªÐ´³Éa[i]!=0 
		for (int i=0;i<l;i++)
		{
			if (a[i]=='(' || a[i]=='[')
				s.push(a[i]);
			else if (a[i]==')' || a[i]==']')
			{
				if (!s.empty() && a[i]==')' && s.top()=='(')
					s.pop();
				else if (!s.empty() && a[i]==']' && s.top()=='[')
					s.pop();
				else
				{
					flag=false;
					break;
				}
			}
		}
		if (flag&&s.empty())
		{
			printf ("Yes\n");
		}
		else
		{
			printf ("No\n");
		}
	} 
	return 0;
}