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