Morris' Blog

2012-01-26 17:56:54Morris

[UVA] 673 - Parentheses Balance

留言 0 收藏 0 推薦 0

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

括弧匹配

實做 : stack

#include<stdio.h>
int Check(char *s) {
   int i, stack[200], idx = -1;
   for(i = 0; s[i]; i++) {
       switch(s[i]) {
           case '(':
               stack[++idx] = '(';
               break;
           case '[':
               stack[++idx] = '[';
               break;
           case ')':
               if(idx < 0)       return 0;
               if(stack[idx] == '(')   idx--;
               else   return 0;
               break;
           case ']':
               if(idx < 0)       return 0;
               if(stack[idx] == '[')   idx--;
               else   return 0;
               break;
       }
   }
   if(idx == -1)   return 1;
   return 0;
}
int main() {
   int T;
   char s[200];
   scanf("%d", &T);
   getchar();
   while(T--) {
       gets(s);
       if(Check(s) == 0)
           puts("No");
       else
           puts("Yes");
   }
    return 0;
}

上一篇：[UVA] 440 - Eeny Meeny Moo

下一篇：[UVA] 10245 - The Closest Pair Problem