UVA - 673 - Parentheses Balance (창고 의 응용!)

UVA - 673
Parentheses Balance
Time Limit: 3000MS
 
Memory Limit: Unknown
 
64bit IO Format: %lld & %llu
Submit Status
Description
  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 

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

Sample Output 

Yes
No
Yes

Miguel Revilla 2000-08-14
Source
Root :: Competitive Programming: Increasing the Lower Bound of Programming Contests (Steven & Felix Halim) :: Chapter 2. Data Structures and Libraries :: Data Structures With Built-in Libraries ::  STL stack
Root :: Competitive Programming 2: This increases the lower bound of Programming Contests. Again (Steven & Felix Halim) :: Data Structures and Libraries :: Linear Data Structures with Built-in Libraries ::  C++ STL stack (Java Stack)
Root :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: Rare Topics :: Rare Problems ::  Bracket Matching
Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: Volume 2. Data Structures ::  Lists
Root :: AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu) :: Chapter 6. Data Structures ::  Exercises
간단 한 스 택 의 응용.
빈 문 자 를 보지 못 했 습 니 다. WA 는 두 번 입 니 다.
AC 코드:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;

int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		getchar();
		while(n--)
		{
			char a[130];
			stack<char> s;
			gets(a);
			int flag = 0;
			for(int i=0; a[i] != '\0'; i++)
			{
				if(a[i] == '(' || a[i] == '[') s.push(a[i]);
				else if(a[i] == ')') 
				{
					if(!s.empty() && s.top() == '(') s.pop();
					else { flag = 1; break; }
				}
				else if(a[i] == ']')
				{
					if(!s.empty() && s.top() == '[') s.pop();
					else { flag = 1; break; }
				}
			}
			if(flag || !s.empty()) printf("No
");
			else printf("Yes
");
		}
	}
	return 0;
}