最小删除以在C ++中制作有效的括号

假设我们有一个字符串s'（'，'）'和小写英文字符。我们必须删除最小括号（在任何位置的'（'或'）'），以便得到的括号字符串有效并返回任何有效字符串。当满足所有这些条件时，括号字符串有效-

• 它是空字符串，仅包含小写字符，或者

• 它可以写为AB（A与B串联）的形式，其中A和B是有效字符串，或者

• 它可以以(A)的形式编写，其中A是有效字符串。

因此，如果输入类似于“ a）b(c)d”，那么输出将为“ ab(c)d”

为了解决这个问题，我们将遵循以下步骤-

• 定义一个堆栈st

• 对于范围从0到s的i

• 如果堆栈不为空，则从堆栈弹出，否则s [i] ='*'

• 如果s [i] ='（'，则将i插入st

• 否则，当s [i]为'）'时，

• 虽然st不为空，

• s [堆栈的顶部元素] ='*'

• 从堆栈弹出

• ans：=空字符串

• 当我的范围是0到s的大小– 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