UVa_00673_Parentheses_Balance.cpp

Problem Links:

uva00673,

Problem:

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

Solution:
Using stack to check the next element with the top element in the stack.
Keep getting the WA, until I used getline instead of cin. There might be some space in the string. But the problem description doesn't mention that. It's so weird.

Source Code:

//Tue Apr 26 01:15:40 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

bool check(string s) {
    int N = s.size();
    if (N % 2 == 1)
        return false;
    stack<char> list;
    for (int i = 0; i < N; i++) {
        if (s[i] == '(' || s[i] == '[')
            list.push(s[i]);
        else if (s[i] == ')') {
            if (list.size() > 0 && list.top() == '(')
                list.pop();
            else
                return false;
        } else if (s[i] == ']') {
            if (list.size() > 0 && list.top() == '[')
                list.pop();
            else
                return false;
        }
    }
    if (list.size() != 0)
        return false;
    return true;
}

int main(int argc, char* argv[]) {
//  freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    int N;
    cin >> N;
    getchar();
    while (N--) {
        string s;
        getline(cin, s, '\n');
        if (check(s))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    //  fclose(stdin);
    //fclose(stdout);
    return 0;
}