#UVa:673-Parentheses Balance

灆洢 2012-01-17 21:40:32

利用Stack解括弧匹配的方法解即可。

C++(0.052)

/*******************************************************/
/* UVa 673 Parentheses Balance                         */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/01/17                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;

int main(){
  int n;
  string s;
  stack<char> stk;
  bool correct;
  while( scanf( "%d", &n ) != EOF ){
    getchar();
    for( int i = 0 ; i < n ; i++ ){
      getline( cin, s );
      correct = 1;
      while( !stk.empty() ) stk.pop();
      for( int j = 0 ; j < s.length() ; j++ ){
        if( s[j] == '(' || s[j] == '[' )
          stk.push( s[j] );
        else if( s[j] == ')' ){
          if( stk.empty() || stk.top() != '(' ){
            correct = 0;
            break;
          }
          stk.pop();
        }
        else if( s[j] == ']' ){
          if( stk.empty() || stk.top() != '[' ){
            correct = 0;
            break;
          }
          stk.pop();
        }
      }
      if( !stk.empty() ) correct = 0;
      printf( ((correct)?"Yes\n":"No\n") );
    }
  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料