گھٽ ۾ گھٽ برڪ ريورسز


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon فاتح
پنگتي حيثيت رکي ٿو چتي اسٽرنگ

گهٽ ۾ گهٽ بریکٹ ريورس ڪرڻ جي مسئلي ۾ ، اسان هڪ ڏنو آهي جملو s صرف اکرن جي اظهار تي مشتمل آهي '{' ۽ '}' صرف. گهٽ ۾ گهٽ تعداد کي بريڪٽ ريورسز جي ڳولا ڪريو هڪ اظهار متوازن ٺاهڻ جي لاءِ.

گھٽ ۾ گھٽ برڪ ريورسز

مثال

داخل: س = “} {”

پيداوار: 2

داخل: س = “{{{“

پيداوار: ڏنل اظهار متوازن نه ٿي سگھي.

گھٽ ۾ گھٽ برقي ريورسز لاءِ الورگيتم

  1. ھڪڙي اسٽرنگ کي شروع ڪريو جنهن ۾ صرف اکرن جا اکر شامل آھن "{" ۽ "}"
  2. چڪاس ڪريو ته اسٽرنگ موڊ 2 جو سائز 0 جي برابر نه آھي ، واپسي -1.
  3. ايلس ٺاهي اي اسٽيڪ ڊيٽا جو structureانچو.
  4. ڏنل اسٽرنگ ذريعي ڳوڙها ڪريو ۽ چيڪ ڪريو ته ڇا اسٽرنگ جي موجوده انڊيڪس ۾ ڪردار '}' جي برابر نه آهي يا اسٽيڪ جي سائيز 0 آهي ، اسٽيڪ جي موجوده انڊيڪس تي ڪردار کي دٻايو ٻئي طرف چيڪ ڪريو ته ڇا اسٽيڪ جي چوٽي تي عنصر آهي '{' ، اسٽيڪ جي چوٽي تي پاپ ڪريو ٻئي کي اسٽيڪ جي تار جي موجوده انڊيڪس تي ڪردار کي دٻايو
  5. انٽيگر متغير ٺاهيو ۽ ان ۾ اسٽيڪ جي سائيز کي ذخيرو ڪريو. ان کان علاوه ، برٽرز جي ڳڻپ ڪرڻ ۽ 0 جي طور تي ان کي ابتدا ڪرڻ لاءِ هڪ نقاد متغير ٺاهيو.
  6. لڪايو جڏهن اسٽيڪ خالي ناهي ۽ اسٽيڪ جي چوٽي تي عنصر برابر آهي {{} ، اسٽيڪ جي چوٽي تي عنصر کي پاپ ڪريو ۽ 1 کي ڪائونٽر کي وڌايو.
  7. انٽيگر ڊيوٽي ورهايو جنهن ۾ اسٽيڪ جي سائيز پهريان 2 کي اسٽور ڪيو ويو ۽ ان کي ڪنٽرري موڊ 2 ۾ شامل ڪيو ويو XNUMX شامل ڪرڻ کانپوءِ نتيجو واپس ڪيو.
  8. چيڪ ڪريو ته ڇا ريٽ ٿيل قيمت -1 جي برابر آھي ، پرنٽ “ڏنل بيان کي توازن نه ٿي ڪري سگھجي” ٻي صورت ۾ موٽندڙ قدر کي پرنٽ ڪريو.

گهٽ ۾ گهٽ بریکٹ ريورسز لاءِ سي ++ پروگرام

#include<bits/stdc++.h> 
using namespace std; 

int MinReversals(string s){ 
    int len = s.length(); 
    
    if(len%2){ 
        return -1;
    }
    
    stack<char> st; 
    
    for(int i=0; i<len; i++){ 
        if(s[i]=='}' && !st.empty()){
        
            if(st.top()=='{'){ 
                st.pop(); 
            }
            
            else{
                st.push(s[i]); 
            }
        } 
        else{
            st.push(s[i]); 
        }
    } 
    
    int red_len = st.size(); 
    int n = 0; 
    
    while(!st.empty() && st.top() == '{'){ 
        st.pop(); 
        n++; 
    } 
    
    return (red_len/2 + n%2); 
} 

int main(){ 
    string s = "}}{{"; 
    
    if(MinReversals(s) == -1){
        cout << "The given expression can not be balanced."; 
    }
    else{
        cout << MinReversals(s);
    }
    
    return 0; 
}
2

جاوا پروگرام گهٽ ۾ گهٽ برڪ ريورسز لاءِ

import java.util.Stack; 
  
class countMinReversals{ 
  
    static int MinReversals(String s){ 
        int len = s.length(); 
      
        if(len%2 != 0){ 
            return -1; 
        }
      
        Stack<Character> st = new Stack<>(); 
          
        for(int i=0; i<len; i++){ 
            char c = s.charAt(i); 
            
            if(c =='}' && !st.empty()){ 
                if(st.peek()=='{'){ 
                    st.pop(); 
                }
                else{
                    st.push(c); 
                }
            } 
            else{
                st.push(c);
            }
        } 
      
        int red_len = st.size(); 
        int n = 0; 
        
        while(!st.empty() && st.peek() == '{'){ 
            st.pop(); 
            n++; 
        } 
      
        return(red_len/2 + n%2); 
    } 
      
    public static void main(String[] args){ 
        String s = "}}{{"; 
          
        if(MinReversals(s) == -1){
            System.out.println("The given expression can not be balanced."); 
        }
        else{
            System.out.println(MinReversals(s));
        }  
    } 
  
}
2

گهٽ ۾ گهٽ برڪ ريورسز لاءِ پيچيدگي تجزيو

وقت جي پيچيدگي: O (n) جتي n ڏنل بيان ۾ ڪردارن جو تعداد آهي.

خلائي پيچيدگي: اي (ن) ڇاڪاڻ ته اسان اين اکرن لاءِ جڳهه استعمال ڪئي آهي.

حوالا