மாற்றத்துடன் சமச்சீர் வெளிப்பாடு


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

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

மாற்றத்துடன் சமச்சீர் வெளிப்பாடு

உதாரணமாக

உள்ளீடு 

s = “{(x [x])}”

வெளியீடு

 ஆம்

உள்ளீடு

s = “[{x} (x)]”

வெளியீடு 

இல்லை

அல்காரிதம்

சமநிலைப்படுத்தப்பட்ட வெளிப்பாட்டின் சிக்கல் அறிக்கையுடன் இப்போது எங்களுக்குத் தெரியும். எனவே, தீர்வுக்கான கீழேயுள்ள வழிமுறைக்கு வருகிறோம்.

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

மாற்றத்துடன் சமச்சீர் வெளிப்பாட்டிற்கான சி ++ திட்டம்

#include <bits/stdc++.h> 
using namespace std; 
  
int isMatching(char a, char b){ 
    if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x') 
      return 1; 
    return 0; 
} 
  
int isBalanced(string s, stack<char> ele, int ind){ 
  
    if(ind == s.length()){  
        return ele.empty();
    }
  
    char topEle; 
  
    int res; 
  
    if((s[ind] == '{') || (s[ind] == '(') || (s[ind] == '[')){ 
        ele.push(s[ind]); 
        return isBalanced(s, ele, ind + 1); 
    } 
  
    else if((s[ind] == '}') || (s[ind] == ')') || (s[ind] == ']')){ 
  
        if(ele.empty()){  
            return 0; 
        }
  
        topEle = ele.top(); 
        ele.pop(); 
  
        if(!isMatching(topEle, s[ind])){  
            return 0; 
        }
          
        return isBalanced(s, ele, ind + 1); 
    } 
  
    else if(s[ind] == 'x'){ 
        stack<char> tmp = ele; 
        tmp.push(s[ind]); 
        res = isBalanced(s, tmp, ind + 1); 
        if(res){ 
            return 1;
        }
        if(ele.empty()){ 
            return 0; 
        }
        ele.pop();
        
        return isBalanced(s, ele, ind + 1); 
    } 
} 
  
int main(){ 
    string s = "{(x[x])}"; 
    stack<char> ele;
    
    if(isBalanced(s, ele, 0)){  
        cout<<"Yes";   
    }
    
    else{ 
        cout<<"No";
    }
    return 0; 
}
Yes

மாற்றத்துடன் சமச்சீர் வெளிப்பாட்டிற்கான ஜாவா திட்டம்

import java.util.Stack; 
  
class BalancedExpression{ 
    
    static int isMatching(char a, char b){ 
        if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x'){ 
            return 1; 
        } 
        return 0; 
    } 
  
    static int isBalanced(String s, Stack<Character> ele, int ind){ 
  
        if(ind == s.length()){ 
            if(ele.size() == 0){ 
                return 1; 
            } 
            else{ 
                return 0; 
            } 
        } 
  
        char topEle; 
  
        int res; 
  
        if((s.charAt(ind) == '{') || (s.charAt(ind) == '(') || (s.charAt(ind) == '[')){ 
            ele.push(s.charAt(ind)); 
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if((s.charAt(ind) == '}') || (s.charAt(ind) == ')') || (s.charAt(ind) == ']')){ 
  
            if(ele.size() == 0){ 
                return 0; 
            } 
  
            topEle = ele.peek(); 
            ele.pop(); 
  
            if(isMatching(topEle, s.charAt(ind)) == 0){ 
                return 0; 
            } 
  
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if(s.charAt(ind) == 'x'){ 
            Stack<Character> tmp = new Stack<>(); 
            
            tmp.addAll(ele);  
            tmp.push(s.charAt(ind)); 
            res = isBalanced(s, tmp, ind + 1); 
            
            if(res == 1){ 
                return 1; 
            } 
            
            if(ele.size() == 0){ 
                return 0; 
            } 
            
            ele.pop(); 
            return isBalanced(s, ele, ind + 1); 
        } 
        return 1; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "{(x[x])}"; 
        Stack<Character> ele = new Stack<Character>(); 
  
        if(isBalanced(s, ele, 0) != 0){ 
            System.out.println("Yes"); 
        } 
        
        else{ 
            System.out.println("No"); 
        } 
    } 
}
Yes

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது: O ((2 ^ n) * n) இங்கு n என்பது சரத்தின் நீளம்.

துணை இடம்: O (n) ஏனெனில் நாங்கள் n கூடுதல் இடத்தை அடுக்கில் பயன்படுத்தினோம்.

குறிப்புகள்