首页 > 代码库 > uva673

uva673

  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

这是一道模拟题,注意空行的处理即可

#include <iostream>
#include <stack>
#include <string>
#include <map>
using namespace std;

map<char, char> m;
stack<char> st1;
int main(void){
	string s;
	int num;
	int flag;

#ifndef ONLINE_JUDGE
	freopen("f:\\infile.txt", "r", stdin);
#endif
	
	m['('] = ')';
	m['['] = ']';
	cin >> num;
	cin.ignore(10, '\n');
	while(num--){
		getline(cin, s);

		flag = 0;
		while(st1.size())
			st1.pop();
		for(int i = 0; i < s.size(); i++){
			if((s[i] == '(') || (s[i] == '['))
				st1.push(s[i]);
			else if(st1.size() && (s[i] == m[st1.top()])){
					st1.pop();
			}
			else{
				flag = 1;
				break;
			}
		}
		if(flag == 1){
			cout << "No" << endl;
			continue;
		}
		if(!st1.size())
			cout << "Yes";
		else
			cout << "No";
//		if(num != 0)
		cout << endl;	
	}
	return 0;
}