指定された位置に開き角かっこが含まれるようなC++のバランスの取れた式

括弧のバランスの取れた式は、すべての種類の括弧のペアを正しい順序で一緒に含む式です。これは、すべての開き括弧に対して、適切な括弧の順序で閉じ括弧があることを意味します。つまり、{}。

表現 − {（[] [] {}）（{} [] {}）}

出力 −バランスの取れた

ここで、この問題では、指定された数の角かっこから可能なすべてのバランスの取れた式を作成する必要があります。条件は、指定された位置に開き角かっこがあることです。

この問題では、整数nと長さ2nのブラケットの位置の配列が与えられ、開始ブラケットでマークされた位置が開始ブラケットを持つように、長さ2nのバランスの取れた式の数を見つける必要があります。 {'。

例 −

Input : n = 2 , position [1, 0 , 0 , 0].
Output : 2
Explanation : All possible outcomes are : {{}} , {}{}.

アルゴリズム

• 1つある位置はすべて、角かっこで囲まれています。

• 次のルールを使用して再帰ループを使用します

  • （開き角かっこ数-閉じかっこ数）> 0の場合、0を返します。

  • nまでループした後、プッシュとポップ後の括弧の合計が0の場合、1を返します。つまり、得られたソリューションです。それ以外の場合は0を返します。

  • 式に1が事前に割り当てられている場合は、インデックスを増やして再帰的に呼び出し、角かっこの総数を増やします。

  • それ以外の場合は、インデックスの場所に開いたブラケットを挿入して関数を再帰的に呼び出してから、閉じたブラケットを挿入し、ブラケットの総数を減らして次のインデックスに移動します。

プログラム

#include <bits/stdc++.h>
using namespace std;
int find(int index, int openbrk, int n, int expression[]){
   if (openbrk < 0)
      return 0;
   if (index == n){
      if (openbrk == 0)
         return 1;
      else
         return 0;
   }
   if (expression[index] == 1) {
      return find(index + 1, openbrk + 1, n, expression);
   } else {
      return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
   }
}
int main() {
   int n = 3;
   int expression[6] = { 1, 0, 1, 0, 0, 0};
   cout << find(0, 0, 2 * n, expression) <<endl;
   return 0;
}

出力

3