C++の置換によるバランスの取れた式

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

概念をよりよく理解するためにいくつかの例を見てみましょう-

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

出力 −バランスの取れた

説明 −開き括弧ごとに閉じ括弧があることがわかります。ペアの開き括弧と閉じ括弧の間にあるすべての括弧。

出力 −バランスが取れていない

説明 −式のバランスを崩す、順序付けられていない括弧のペアがいくつかあります。

置換による式のバランスと呼ばれるこの問題では 、これらの角かっこ‘{’、‘}’、‘[’、‘]’、‘（’、‘）’の式を含む文字列が与えられます。角かっこが欠落していて、代わりに「*」が配置されている場所がいくつかあります。また、すべてのアスタリスク記号を適切な角かっこで置き換えると、指定された式が有効な式になる可能性があるかどうかを確認する必要があります。

例

入力 − exp =“ {[*（*）]}”

出力 −表現のバランスをとることができます

説明 −置き換える必要のあるシンボルが2つあります。そして、交換すると{[（（））]}

入力 − exp =“ [（*）{} {{}}]”

出力 −表現のバランスをとることができません

説明 −置き換える必要のあるシンボルが1つあります。また、*を角かっこで置き換えると、式のバランスをとることができません。

これで、問題を明確に理解できたので、この問題の解決策を生成できます。特定の括弧式のバランスが取れているかどうかを確認するために、スタックデータ構造を使用してタスクを実行します。

このタスクを実行するために実行される操作は-

• 文字列式のすべての要素をトラバースして、-

  を実行します

• 式で開き角かっこが見つかった場合、つまり「{」、「[」、「（」の場合は、要素をスタックにプッシュします。

• 式で閉じ括弧が見つかった場合、つまり「}」、「]」、「）」。スタックの一番上にある要素をポップし、これが検出された閉じ括弧に一致する開口部であるかどうかを確認します。

  • 両方の括弧が一致した場合は、式の次の要素に移動します（ステップ1）。

  • 両方の括弧が一致しない場合、式はバランスが取れていません。

• 式で*が検出された場合、これは開始ブラケットと終了ブラケットの両方になります。次に、

  • 最初にそれを開始ブラケットとして扱い、スタックにプッシュし、次の要素の再帰呼び出しを使用して一致する終了ブラケットを見つけます。これにより問題が発生する場合は、次の手順に従ってください

  • 閉じ括弧として扱います。スタックの一番上と一致する必要があり、スタックの一番上をポップします。

  • *の終了値が、バランスの取れていない開始リターンと一致しません。

• 結果に基づいてステートメントを印刷します。

#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b){
   if ((a == '{' &amp; b == '}') || (a == '[' &amp; b == ']') || (a == '(' &amp; b == ')') || a == '*')
      return 1;
   return 0;
}
int isBalancedexpression(string s, stack<char> ele, int ind){
   if (ind == s.length())
      return ele.empty();
   char topEle;
   int res;
   if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
      ele.push(s[ind]);
      return isBalancedexpression(s, ele, ind + 1);
   }
   else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
      if (ele.empty())
         return 0;
      topEle = ele.top();
      ele.pop();
      if (!isMatching(topEle, s[ind]))
         return 0;
      return isBalancedexpression(s, ele, ind + 1);
   }
   else if (s[ind] == '*') {
      stack<char> tmp = ele;
      tmp.push(s[ind]);
      res = isBalancedexpression(s, tmp, ind + 1);
      if (res)
         return 1;
      if (ele.empty())
         return 0;
      ele.pop();
      return isBalancedexpression(s, ele, ind + 1);
   }
}
int main(){
   string s = "{[*(*)]}";
   stack ele;
   if (isBalancedexpression(s, ele, 0))
      cout << "Balanced";
   else
      cout << "Not Balanced";
   return 0;
}

Balanced