C++でバランスの取れた括弧シーケンスのペアを数える方法

括弧だけで構成された複数の文字列が与えられ、それらを組み合わせて「バランスの取れた括弧シーケンス」となるペアが何組作れるかを計算するのが課題です。

括弧の並びが「バランスが取れている」とは、開き括弧「(」と閉じ括弧「)」の数が一致している状態を指します。また、一度ペアの形成に使用した文字列を、別のペアのために再び使用することはできません。

入力 − string paran[] = { ")()())", "(", ")(", ")(", ")" }

出力 − バランスの取れた括弧シーケンスのペアの数: 1

説明 − 各文字列を順番に調べていきます。まず最初の要素「)()())」には、開き括弧が2つ、閉じ括弧が4つ含まれています。この文字列と組み合わせてバランスを取るには、余分な開き括弧をちょうど2つ持つ文字列が必要ですが、配列の中にそのような文字列は存在しないため、この候補は破棄して次へ進みます。その結果、開き括弧と閉じ括弧の数が一致する有効なペアは (2, 5) の位置にある1組のみとなり、カウントは1となります。

入力 − string paran[] = { ")()())", "((", "(", ")(", ")(", ")" }

出力 − バランスの取れた括弧シーケンスのペアの数: 2

説明 − 有効なバランスの取れた括弧ペアは (1, 2) と (3, 6) の位置に存在します。したがって、カウントは2となります。

プログラムで使用するアプローチ

• 文字列を入力し、length() 関数を使って文字列の長さを求め、以降の処理のためにデータを関数へ渡します。

• 有効な括弧ペアの数を保持する一時変数 count を用意し、unordered_map 型の変数 um_1 と um_2 を作成します。

• 0から文字列のサイズまで処理を繰り返す FOR ループを開始します。

• ループ内では、str に paran[i]、すなわち括弧配列の i 番目の要素を代入し、改めて文字列の長さを計算します。

• 一時変数として first と last を用意し、両方を 0 で初期化します。

• j を 0 から文字列の長さまで走査する別の FOR ループを開始します。

• ループ内では、str[j] が '(' であれば first を1増やし、そうでない場合に first が1であれば first を1減らし、いずれにも当てはまらなければ last を1増やします。

• 続いて、first が1かつ last が0であれば um_1[first]++ を実行し、last が1かつ first が0であれば um_2[last]++ を実行します。さらに first と last がどちらも0であれば count を1増やします。

• count を count / 2 に更新します。

• um_1 の各要素についてループを行い、count に um_1 の second 値と um_2 の対応する値のうち小さい方を加算します。

• count を返します。

• 結果を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int parentheses(string paran[], int size){
    int count = 0;
    unordered_map<int, int> um_1, um_2;
    for (int i = 0; i < size; i++){
        string str = paran[i];
        int len = str.length();
        int first = 0;
        int last = 0;
        for (int j = 0; j < len; j++){
            if (str[j] == '('){
                first++;
            }
            else{
                if (first==1){
                    first--;
                }
                else{
                    last++;
                }
            }
        }
        if(first==1 && last!=1){
            um_1[first]++;
        }
        if (last==1 && first!=1){
            um_2[last]++;
        }
        if(first!=1 && last!=1){
            count++;
        }
    }
    count = count / 2;
    for (auto it : um_1){
        count += min(it.second, um_2[it.first]);
    }
    return count;
}
int main(){
    string paran[] = { ")()())", "(", ")(", ")(", ")"};
    int size = sizeof(paran) / sizeof(paran[0]);
    cout<<"Count of pairs of parentheses sequences such that parentheses are balanced are:
"<<parentheses(paran, size);
}

出力

上記のコードを実行すると、次の出力が得られます −

Count of pairs of parentheses sequences such that parentheses are balanced are: 1