ลบขั้นต่ำเพื่อสร้างวงเล็บที่ถูกต้องใน C ++

สมมติว่าเรามีสตริง s ของ '(' , ')' และอักขระภาษาอังกฤษตัวพิมพ์เล็ก เราต้องลบจำนวนวงเล็บขั้นต่ำ ( '(' หรือ ')' ในตำแหน่งใดๆ ) เพื่อให้สตริงที่เป็นผลลัพธ์ถูกต้องและส่งคืนสตริงที่ถูกต้อง สตริงวงเล็บจะใช้ได้เมื่อตรงตามเกณฑ์ทั้งหมด -

• เป็นสตริงว่าง มีเฉพาะอักขระตัวพิมพ์เล็กเท่านั้น หรือ

• สามารถเขียนเป็นรูป AB (A ต่อด้วย B) โดยที่ A และ B เป็นสตริงที่ถูกต้อง หรือ

• สามารถเขียนเป็นรูปของ (A) โดยที่ A เป็นสตริงที่ถูกต้อง

ดังนั้นหากอินพุตเป็นเหมือน “a)b(c)d” ผลลัพธ์จะเป็น “ab(c)d”

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดสแต็ก st

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ s

  • ถ้า s[i] ='(' ให้ใส่ i ลงใน st

  • มิฉะนั้นเมื่อ s[i] คือ ')' แล้ว

    • ถ้า stack ไม่ว่าง ให้ป๊อปจาก stack มิฉะนั้น s[i] ='*'

• ในขณะที่ st ไม่ว่างเปล่า

  • s[องค์ประกอบด้านบนของสแต็ก] ='*'

  • ป๊อปจากสแต็ก

• ตอบ :=สตริงว่าง

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาด s – 1

  • ถ้า 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