C++에서 유효한 괄호를 만들기 위한 최소 제거

'(' , ')' 및 소문자 영어 문자의 문자열 s가 있다고 가정합니다. 결과 괄호 문자열이 유효하고 유효한 문자열을 반환하도록 최소 개수의 괄호( '(' 또는 ')', 임의의 위치)를 제거해야 합니다. 괄호 문자열은 이러한 기준이 모두 충족될 때 유효합니다 -

• 빈 문자열이거나 소문자만 포함하거나

• A와 B가 유효한 문자열인 AB(A와 B가 연결된) 형식으로 작성할 수 있습니다. 또는

• (A) 형식으로 작성할 수 있으며 여기서 A는 유효한 문자열입니다.

따라서 입력이 "a)b(c)d"와 같으면 출력은 "ab(c)d"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 스택 정의

• 범위 0에서 s 크기의 i에 대해

  • s[i] ='('이면 i를 st

    에 삽입합니다.

  • 그렇지 않으면 s[i]가 ')'일 때

    • 스택이 비어 있지 않으면 스택에서 팝, 그렇지 않으면 s[i] ='*'

• st가 비어 있지 않은 동안

  • s[스택의 최상위 요소] ='*'

  • 스택에서 팝

• ans :=빈 문자열

• 범위 0에서 s – 1까지의 i에 대해

  • s[i]가 '*'가 아니면 ans :=ans + s[i]

• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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