AOJ 1173 The Balance of the World

問題

The Balance of the World | Aizu Online Judge

• 与えられた文について丸カッコと角カッコの対応が取れているか調べよ
• なお、カッコのペアで囲まれた部分文字列についても対応が取れないといけない

方針

• 与えられた文字列について、任意の位置で左カッコの数が常に右カッコの数以上であり、文字列全体では右カッコと左カッコの数が同数かどうか調べる
• 同数である場合、カッコで囲まれた各部分文字列について、囲んでいるのとは違う種類のカッコについて、右カッコと左カッコの数が同数かどうか調べる（日本語力が足りない…）

コード

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(int i=0; i<(n); ++i)

bool isBalancedS(const string &s) {
    int cnt = 0;
    rep(i, s.size()) {
        if(s[i] == '[') cnt++;
        if(s[i] == ']') cnt--;
        if(cnt < 0) return false;
    }
    if(cnt > 0) return false;
    return true;
}
bool isBalancedR(const string &s) {
    int cnt = 0;
    rep(i, s.size()) {
        if(s[i] == '(') cnt++;
        if(s[i] == ')') cnt--;
        if(cnt < 0) return false;
    }
    if(cnt > 0) return false;
    return true;
}

bool isBalanced(const string &s) {
    if(!isBalancedS(s)) return false;
    if(!isBalancedR(s)) return false;
    // check substring
    for(int i=0; i<s.size(); ++i) {
        if(s[i] == '(') {
            int len = 0;
            int cnt = 1;
            for(int j=i+1; j<s.size(); ++j, ++len) {
                if(s[j] == '(') cnt++;
                if(s[j] == ')') cnt--;
                if(cnt==0) break;
            }
            if(!isBalancedS(s.substr(i+1, len))) return false;
        } else if(s[i] == '[') {
            int len = 0;
            int cnt = 1;
            for(int j=i+1; j<s.size(); ++j, len++) {
                if(s[j] == '[') cnt++;
                if(s[j] == ']') cnt--;
                if(cnt==0) break;
            }
            if(!isBalancedR(s.substr(i+1, len))) return false;
        }
    }
    return true;
}

int main(void){
    string s;
    while(getline(cin, s) && s!=".") {
        if(isBalanced(s)) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1891606

反省

• ([)]みたいな部分文字列について対応が取れていない例を調べるのに手間取った
• スタックに積むのが正しい解法っぽい（お前は形式言語理論で何を学んだんだ）

スタックを使った解法

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(int i=0; i<(n); ++i)

int main(void){
    string s;
    char bra[] = {'(', ')', '[', ']'};
    while(getline(cin, s) && s!=".") {
        stack<char> stk;
        bool ok = true;
        rep(i, s.size()) {
            bool is_bracket = false;
            rep(j, 4) if(s[i] == bra[j]) is_bracket = true;
            if(!is_bracket) continue;
            if(stk.empty() || s[i] == '(' || s[i] == '[') stk.push(s[i]);
            else if( (stk.top() == '(' && s[i] == ')') ||
                     (stk.top() == '[' && s[i] == ']') ) stk.pop();
            else {
                ok = false;
                break;
            }
        }

        if(ok && stk.empty()) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1891639