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. Yourprogram can assume that the maximum string length is 128.InputThe file contains a positive integer n and a sequence of n strings of parentheses ‘()’ and ‘[]’, one stringa line.OutputA sequence of ‘Yes’ or ‘No’ on the output file.

Sample Input

3

([])

(([()])))

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

Sample Output

Yes

No

Yes

问题链接：

问题简述：参见上文。

问题分析：这个是一个括号匹配问题，自然需要用堆栈。

程序说明：

输入方面用字符流是最佳的方案。

堆栈就没有必要用STL的堆栈（时间上慢），自己简单用数组实现一个堆栈是轻而易举的事情。

题记：（略）

参考链接：（略）

AC的C语言程序如下：

/* UVA673 Parentheses Balance */#include 
    
     #define N 128char stack[N];int ps;int main(void){    int n;    char c;    scanf("%d", &n);    getchar();    while(n--) {        ps = 0;        while((c = getchar()) != '\n') {            if(ps > 0) {                if((stack[ps - 1] == '(' && c == ')') || (stack[ps - 1] == '[' && c == ']'))                    ps--;                else                    stack[ps++] = c;            } else                stack[ps++] = c;        }        printf("%s\n", (ps > 0) ? "No" : "Yes");    }    return 0;}