ZeroJudge E924: Pairing Brackets

Please write a program that takes in a string of characters and outputs whether the parentheses in that string are correctly matched.
The parentheses to be checked include round brackets (), square brackets [], angle brackets, and curly brackets {}.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains a positive integer T (1 ≤ T ≤ 1000), representing the number of strings to be validated.
Then, there are T lines, each containing a string s to be validated for parentheses matching. The strings will only contain ()[], , and {}.		If the matching is successful, output "Y".
If the matching fails, output "N".
4
{()<>}[]
(){
{(})
())		Y
N
N
N

Thought Process

If the length of the string is odd, output "N" directly. You can solve this problem using the concept of a stack. If the character encountered is a left parenthesis, push this character into a vector. If it's a right parenthesis, check if the last element in the vector can be paired with this right parenthesis. If the pairing is successful, use pop_back to delete the last element from the vector. If the pairing fails, output "N" directly and break out of the for loop. Additionally, when checking, also make sure if the vector is empty. If the size of the vector is 0, it means a right parenthesis appeared suddenly, so output "N" directly and break. After the for loop ends, also check if there are any remaining left parentheses in the vector. If there are any, output "N" similarly.

Sample Code－ZeroJudge E924: Pairing Brackets

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    map<char, char>MAP;
    MAP[')'] = '(';
    MAP[']'] = '[';
    MAP['>'] = '<';
    MAP['}'] = '{';
    for (int i = 0; i<N; i++)
    {
        string str;
        cin >> str;
        if (str.length() % 2 != 0) cout << "N\n";
        else
        {
            vector<char>v;
            bool ok = true;
            for (int j = 0; j<str.length(); j++)
            {
                char ch = str[j];
                if (ch == '(' || ch == '[' || ch == '<' || ch == '{') v.push_back(ch);
                else
                {
                    if (v.size() == 0)
                    {
                        ok = false;
                        cout << "N\n";
                        break;
                    }
                    if (v[int(v.size())-1] == MAP[str[j]]) v.pop_back();
                    else
                    {
                        ok = false;
                        cout << "N\n";
                        break;
                    }
                }
            }
            if (ok && v.size() != 0) cout << "N\n";
            else if (ok) cout << "Y\n";
        }
    }
}

//ZeroJudge E924
//Dr. SeanXD
Tags

Related Posts

Comments