ஒரு வெளிப்பாட்டில் சமப்படுத்தப்பட்ட அடைப்புக்குறிக்குள் சரிபார்க்கவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் உயர்வு ஆரக்கிள் Snapdeal வால்மார்ட் ஆய்வகங்கள் விப்ரோ யாத்ரா ஸோகோ
ஸ்டேக் சரம்

கொடுக்கப்பட்ட ஒரு சரம் கள் நீளம் n. ஒவ்வொரு திறப்பு அடைப்புக்குறிப்பிற்கும் ஒரு மூடு அடைப்பு உள்ளதா என்பதைச் சரிபார்க்கவும், அதாவது அனைத்து அடைப்புக்குறிகளும் சமநிலையில் இருந்தால். வேறு வார்த்தைகளில் கூறுவதானால், ஒவ்வொரு '{', '(' மற்றும் '[' முறையே ஒரு '}', ')' மற்றும் ']' இருந்தால், வெளிப்பாடு சமநிலையானது என்று கூறப்படுகிறது.

உதாரணமாக -

“{[()] The” என்ற வெளிப்பாடு சீரான அடைப்புக்குறிப்புகளைக் கொண்டுள்ளது, ஏனெனில் இது ஒரு தொடக்க அடைப்புக்குறிக்கு ஒருவித மூடு அடைப்புக்குறிப்பைக் கொண்டுள்ளது.

ஒரு வெளிப்பாட்டில் சமப்படுத்தப்பட்ட அடைப்புக்குறிக்குள் சரிபார்க்கவும்

உதாரணமாக

உள்ளீடு: s = “[()] {} {[() ()] ()}”

வெளியீடு: வெளிப்பாடு சீரானது.

உள்ளீடு: s = “[() {}”

வெளியீடு: வெளிப்பாடு சமநிலையில் இல்லை.

முறை

முதலில், நாங்கள் ஒரு அடுக்கை உருவாக்குகிறோம். ஒவ்வொரு எழுத்துக்கும் இது ஒரு தொடக்க அடைப்புக்குறிப்பாக இருக்கிறதா என்று சரிபார்க்கவும், அதாவது '{', '(' அல்லது '[', எழுத்தை அடுக்கில் தள்ளுங்கள். இல்லையெனில் அது ஒரு மூடு அடைப்புக்குறிப்பாக இருந்தால், அதாவது '}', ')' அல்லது '] ', அடுக்கின் மேற்பகுதி ஒத்த வகையான அடைப்புக்குறிகளைத் திறக்கிறதா என்று சரிபார்த்து, அதை அடுக்கிலிருந்து பாப் செய்து அடுத்த எழுத்துக்களுக்கான சுழற்சியைத் தொடரவும். வேறு தவறானது. கடைசியில் ஸ்டேக் காலியாக இருந்தால், இதன் அர்த்தம் வெளிப்பாட்டில் சீரான அடைப்புக்குறிப்புகள் உள்ளன, இல்லையெனில் அடைப்புக்குறிப்புகள் சமநிலையற்றவை.

அல்காரிதம்

  1. நீளம் n இன் சரம் s ஐத் தொடங்கவும்.
  2. உருவாக்கவும் ஸ்டாக் எழுத்துக்களை சேமிக்க.
  3. சரம் வழியாக பயணித்து, தற்போதைய எழுத்து ஒரு தொடக்க அடைப்புக்குறியாக இருக்கிறதா என்று சரிபார்த்து அதை அடுக்கில் தள்ளி தொடரவும்.
  4. அடுக்கு காலியாக இருந்தால் தவறானது.
  5. மூடும் அடைப்புக்குறியை மாற்றி, அடுக்கின் மேற்புறத்தில் உள்ள எழுத்து திறந்த அடைப்புக்குறி ஒரே மாதிரியானதா என்பதைச் சரிபார்க்கவும். வேறு தவறானது.
  6. அடுக்கு காலியாக இருந்தால் உண்மை திரும்பவும், இல்லையெனில் பொய்யாகவும்.

ஒரு வெளிப்பாட்டில் சீரான அடைப்புக்குறிப்புகளை சரிபார்க்க சி ++ நிரல்

#include<bits/stdc++.h> 
using namespace std; 
  
bool isBalanced(string str){ 
    stack<char> s; 
    char x; 
  
    for(int i=0; i<str.length(); i++){ 
        if(str[i]=='('||str[i]=='['||str[i]=='{'){ 
            s.push(str[i]); 
            continue; 
        }
  
        if(s.empty()) 
           return false; 
  
        switch(str[i]){ 
            case ')': 
      
                x = s.top(); 
                s.pop(); 
                if(x=='{' || x=='[') 
                    return false; 
                break; 
      
            case '}': 
      
                x = s.top(); 
                s.pop(); 
                if(x=='(' || x=='[') 
                    return false; 
                break; 
      
            case ']': 
      
                x = s.top(); 
                s.pop(); 
                if(x =='(' || x == '{') 
                    return false; 
                break; 
        } 
    } 
  
    return (s.empty()); 
} 
  
int main(){ 
    string s = "[()]{}{[()()]()}"; 
  
    if(isBalanced(s)){ 
        cout<<"Expression is balanced."; 
    }    
    else{
        cout<<"Expression is not balanced."; 
    }    
    return 0; 
}
Expression is balanced.

ஒரு வெளிப்பாட்டில் சீரான அடைப்புக்குறிகளை சரிபார்க்க ஜாவா நிரல்

class Parantheses{ 
    
    static class stack{ 
        int top=-1; 
        char items[] = new char[100]; 
        
        void push(char x){ 
            if(top == 99){ 
                System.out.println("Stack full"); 
            }  
            
            else{ 
                items[++top] = x; 
            } 
        } 
    
        char pop(){ 
            if(top == -1){ 
                System.out.println("Underflow error"); 
                return '\0'; 
            }  
            
            else{ 
                char element = items[top]; 
                top--; 
                return element; 
            } 
        } 
    
        boolean isEmpty(){ 
            return (top == -1) ? true : false; 
        } 
    } 
    
    static boolean isPair(char character1, char character2){ 
        if(character1 == '(' && character2 == ')') 
            return true; 
        
        else if(character1 == '{' && character2 == '}') 
            return true; 
        
        else if(character1 == '[' && character2 == ']') 
            return true; 
        
        else
            return false; 
    } 
    
    static boolean isBalanced(char s[]){ 
        stack st=new stack(); 
        
        for(int i=0;i<s.length;i++){ 
        
            if(s[i] == '{' || s[i] == '(' || s[i] == '[') 
                st.push(s[i]); 
            
            if(s[i] == '}' || s[i] == ')' || s[i] == ']'){ 
            
                if (st.isEmpty()){ 
                    return false; 
                }  
                
                else if( !isPair(st.pop(), s[i])){ 
                    return false; 
                } 
            } 
        
        } 
        
        if(st.isEmpty()) 
            return true;
            
        else
            return false; 
    }  
    
    public static void main(String[] args){ 
        char s[] = {'[','(',')',']','{','}','{','[','(',')','(',')',']','(',')','}'}; 
        
        if(isBalanced(s)){ 
            System.out.println("Expression is balanced.");
        }    
        
        else{
            System.out.println("Expression is not balanced.");   
        }
    } 
}
Expression is balanced.

ஒரு வெளிப்பாட்டில் சமச்சீர் அடைப்புக்குறிக்கு சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது: O (n) இங்கு n என்பது கொடுக்கப்பட்ட சரத்தில் உள்ள அடைப்புக்குறிப்புகள் / எழுத்துகளின் எண்ணிக்கை.

துணை இடம்: O (n) இங்கு n என்பது கொடுக்கப்பட்ட சரத்தில் உள்ள அடைப்புக்குறிப்புகள் / எழுத்துகளின் எண்ணிக்கை, ஏனென்றால் இங்கே நாம் n எழுத்துக்களை அடுக்கில் சேமிக்க இடத்தைப் பயன்படுத்தினோம்.

குறிப்புகள்