最小删除以在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