棧，棧橋

棧，棧橋

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



解題思路：用一個棧，存下（和[，然後循環找到）和}與棧頂的符號相對應就彈出棧頂的符號，直到棧中沒有元素，就輸出Yes，否則No




代碼如下：

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
int n;
cin>>n;
cin.get();
while(n--)
{
stack<char> s;
string str;
int flag=0;
getline(cin,str);
for(int i=0;i<str.size();i++)
{
if(str[i]=='['||str[i]=='(') s.push(str[i]);
else if(!s.empty()&&s.top()=='('&&str[i]==')') s.pop();
else if(!s.empty()&&s.top()=='['&&str[i]==']') s.pop();
else flag=1;
}
if(!flag&&!s.size()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}