[伯俊]4889号安定文字列

[伯俊]4889号安定文字列
質問リンク:https://www.acmicpc.net/problem/4889
質問する
左かっこと右かっこからなる文字列を指定します.ここでは、安定した文字列を生成するために最小の演算数を求めたい.安定文字列の定義は次のとおりです.

の空の文字列は安定しています.

Sが安定であれば、{S}も安定した文字列である.

SとTが安定であれば、ST(2文字列の接続)も安定である.

{},{},{}は安定した文字列であるが,{{,{}および{}は安定した文字列ではない.
文字列に対して実行できる演算には、左カッコを右カッコに置き換えるか、右カッコを左カッコに置き換えるかの2つがあります.
入力
入力は複数のデータセットで構成されます.各データセットは1行で構成されます.行の文字列は、左かっこと右かっこで構成されます.文字列の長さは2000を超えず、常に偶数です.
入力した最後の行には、1つ以上の「-」が与えられます.
しゅつりょく
各試験例について、所定の文字列に必要な最小演算数を試験例番号と入出力により安定に置き換える.
問題を理解する
これはカッコペアを正しく実現する問題です.}{を最小演算子{}に変更します.
質問へのアクセス

"{"プッシュ

に入ります

'}'を入力と

になります.

スタックが空の場合、{プッシュに置換、count(置換回数)+1.

emptyでなければ、ポップアップします.

文字列をチェックすると、

スタックが空でない場合、スタック内の個数/2+count

を返します.

空ラーメン、count return.

コード実装(C++)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int bracketChange(string str){
    vector<char> brackets;
    int count = 0;
    for(int i = 0 ; i < str.length() ; i++){
        if(str[i] == '{') brackets.push_back(str[i]);
        else{
            if(brackets.empty()) {
                brackets.push_back('}');
                count++;
            }
            else brackets.pop_back();
        }
    }
    if(!brackets.empty()) return count + (brackets.size() / 2);
    return count;
}

int main(){
    string str;
    int countNum = 0;
    int changeNum;
    while(1){
        cin >> str;
        if(str[0] == '-') break;
        countNum++;
        changeNum = bracketChange(str);
        cout << countNum << ". " << changeNum << "\n";
    }
}

評価
前に解決した問題はスタック問題なので、実現しやすいです.しかもすぐに解けるので満足です.問題に実装案を手書きで書くと、ソリューションは実装に大きく役立つようです.