uva 673 Parentheses Balance

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

3

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

Sample Output

Yes
No
Yes

 

 

---

Miguel Revilla
2000-08-14 題意： 如果有一個'（'那麼就要有一個）與它匹配，如果有一個'['那麼就要有一個']'與它匹配.。如果都滿足，輸出”YES“，else 輸出”NO“. 思路； 建立一個棧，左括號’[‘,'('都入棧，右括號')',']'都出棧依次進行下去，如果棧為空，則滿足條件，輸出“YES”,如果不滿足條件，則輸出”NO“。 代碼：

#include
#include
using namespace std;
int main()
{
    int n;
    scanf(%d,&n);
        getchar();
        while(n--)
        {
            char a[130];
            stack s;
            gets(a);
            int flag=0;
    for(int i=0;a[i]!='';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;
}