exp_temp.cpp

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

bool valid(string cadeia, bool check) {
    int fecha_par = 0, fecha_col = 0, fecha_cha = 0;

    for(int j = 0; j < (int) cadeia.length(); j++) {
        if(cadeia[j] == '(')
            fecha_par++;
        else if(cadeia[j] == ')') {
            if(!fecha_par) {
                fecha_par = 1;
                break;
            }

            fecha_par--;
        }

        if(cadeia[j] == '[')
            fecha_col++;
        else if(cadeia[j] == ']') {
            if(!fecha_col) {
                fecha_col = 1;
                break;
            }

            fecha_col--;
        }

        if(cadeia[j] == '{')
            fecha_cha++;
        else if(cadeia[j] == '}') {
            if(!fecha_cha) {
                fecha_cha = 1;
                break;
            }

            fecha_cha--;
        }
    }

    if(fecha_par != 0 || fecha_col != 0 || fecha_cha != 0)
        return false;
    else {
        if(check)
            return (valid(cadeia.substr(0, cadeia.size()/2), false) && valid(cadeia.substr(cadeia.size()/2, cadeia.size()), false));
        else
            return true;
    }
}

int main() {

    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        string cadeia;
        cin >> cadeia;

        if(valid(cadeia, true))
            cout << "S" << endl;
        else
            cout << "N" << endl;
    }

    return 0;
}