假设我们有一个字符串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
