首页 > 代码库 > uva 673 - Parentheses Balance

uva 673 - Parentheses Balance

  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 

YesNoYes

#include <iostream>#include <stack>#include <cstring>#include <cstdio>#include <string>#include <algorithm>#include <queue>#include <set>#include <map>#include <fstream>#include <stack>#include <list>using namespace std;/**/#define ms(arr, val) memset(arr, val, sizeof(arr))#define N 500#define INF 0x3fffffff#define vint vector<int>#define sint set<int>#define mint map<int, int>#define lint list<int>#define sch stack<char>char s[N];sch sc;int main(){    int n;    bool tag;    cin >> n;    getchar();    while (n--)    {        tag = true;        while (!sc.empty())        {            sc.pop();        }        gets(s);        for (int i = 0; s[i]; i++)        {            if (s[i] == ( || s[i] == [)            {                sc.push(s[i]);            }            else            {                if (!sc.empty())                {                    char ch = sc.top();                    sc.pop();                    if ((s[i] == ) && ch == () || (s[i] == ] && ch == [))                    {                        continue;                    }                }                tag = false;                break;            }        }        if (!sc.empty())        {            tag = false;        }        cout << (tag ? "Yes" : "No") << endl;            }    return 0;}