C++で有効な括弧を作成するための最小削除

'（'、'）'の文字列sと小文字の英語文字があるとします。結果の括弧文字列が有効になり、有効な文字列が返されるように、最小数の括弧（'（'または'）'、任意の位置）を削除する必要があります。括弧文字列は、これらの基準がすべて満たされている場合に有効です-

• 空の文字列であり、小文字のみが含まれている、または

• これは、AB（AとBを連結したもの）の形式として記述できます。ここで、AとBは有効な文字列、または

• （A）の形式で記述できます。ここで、Aは有効な文字列です。

したがって、入力が「a）b（c）d」の場合、出力は「ab（c）d」になります

これを解決するには、次の手順に従います-

• スタックstを定義する

• 0からsのサイズまでの範囲のiの場合

  • s [i] =‘（’の場合、iをstに挿入します

  • それ以外の場合、s [i]が「）」の場合は

    • スタックが空でない場合はスタックからポップし、そうでない場合はs [i] =‘*’

• stが空ではない間、

  • s[スタックの最上位要素]=‘*’

  • スタックからポップ

• ans：=空の文字列

• 0からsのサイズまでの範囲のiの場合– 1

  • s [i]が「*」でない場合、ans：=ans + s [i]

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minRemoveToMakeValid(string s) {
      stack <int> st;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '(')st.push(i);
         else if(s[i] == ')'){
            if(!st.empty())st.pop();
            else s[i] = '*';
         }
      }
      while(!st.empty()){
         s[st.top()] = '*';
         st.pop();
      }
      string ans = "";
     for(int i = 0; i < s.size(); i++){
        if(s[i] != '*')ans += s[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}

入力

"a)b(c)d"

出力

ab(c)d