C ++で括弧のバランスが取れるように、括弧シーケンスのペアをカウントします。

括弧を含む文字列が与えられます。タスクは、括弧のバランスが取れるように形成できる括弧シーケンスのペアの数を計算することです。

開き括弧と閉じ括弧の数が等しい場合、括弧はバランスが取れていると言われます。 1回使用した括弧は、ペアを形成するために2回と見なすことはできません。

入力 − string paran [] ={"）（）（））"、 "（"、 "）（"、 "）（"、 "）"}

出力 −括弧のバランスがとれるような括弧シーケンスのペアの数は次のとおりです。1

説明 −カウントをより適切に計算するために、文字列のすべてのセットを取得します。最初の要素を「）（）（））」と見なします。ここでは、4つの閉じ括弧と2つの開き括弧があるため、2つの閉じ括弧を含む文字列内の次の要素を探して、バランスの取れた括弧シーケンスを作成します。文字列にあるので、それを破棄して次へ進みます。したがって、開き括弧と閉じ括弧が等しい有効なペアは（2、5）であるため、カウントは1です。

入力 − string paran [] ={"）（）（））"、 "（（"、 "（"、 "）（"、 "）（"、 "）"}

出力 −括弧のバランスがとれるような括弧シーケンスのペアの数は次のとおりです。1

説明 −有効なバランス括弧のペアは（1、2）と（3、6）にあります。したがって、カウントは2です。

以下のプログラムで使用されているアプローチは次のとおりです

• 文字列を入力し、length（）関数を使用して文字列の長さを計算し、データを関数に渡してさらに処理します。

• 一時変数カウントを取得して、括弧の有効なペアを格納し、タイプunordered_mapのum_1およびum_2変数を作成します。

• 0から文字列のサイズまで別のループFORを開始します

• ループ内で、strをparan [i]、つまり括弧の最初の要素として設定し、文字列の長さを再度計算します。

• 一時変数を最初と最後として取り、0で初期化します

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

• ループ内で、IF str [j] =‘（‘をチェックしてから最初を1インクリメントします。ELSEをチェックします。IFfirst =1をチェックしてから、最初を1デクリメントします。ELSEは最後を1インクリメントします。

• ここで、IFの最初が1で最後が0であることを確認してからum_1 [first] ++を設定し、IFの最後が1で最初が0であることを確認してからum_2 [lst] ++を設定し、IFの最初が0で最後も0であることを確認してからカウントをインクリメントします1で。

• カウントをカウント/2として設定

• 0からum_1までループを開始し、カウントをum_1.secondとum_2.firstからの最小値として設定します

• カウントを返す

• 結果を印刷します。

例

#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