ආදේශනය සමඟ සමබර ප්‍රකාශනය


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් ඉහළ දැමීම ඔරකල් Snapchat Snapdeal වෝල්මාර්ට් ලැබ් විෙප්රෝ යත්රා Zoho
අඩුක්කුව String

සමතුලිත ප්‍රකාශනය සමඟ ප්‍රතිස්ථාපන ගැටළුව තුළ අපි වරහන් ලබා දී ඇත, එනම් '(', ')', '[', ']', '{', '}'. එම පේළියකි වරහන් වෙනුවට ආදේශකයක් ලෙස සමහර ස්ථානවල x ද අඩංගු වේ. සියලුම x වරහන් වරහන් සමඟ ප්‍රතිස්ථාපනය කිරීමෙන් පසු වලංගු වරහන් සහිත ප්‍රකාශනයක් බවට පරිවර්තනය කළ හැකිදැයි පරීක්ෂා කරන්න.

ආදේශනය සමඟ සමබර ප්‍රකාශනය

උදාහරණයක්

ආදාන 

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

ප්රතිදාන

 ඔව්

ආදාන

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

ප්රතිදාන 

නැත

ඇල්ගොරිතම

සමතුලිත ප්‍රකාශනය සමඟ ප්‍රතිස්ථාපන ගැටලුව පිළිබඳ ප්‍රකාශය දැන් අපි දනිමු. ඉතින්, අපි විසඳුම සඳහා පහත ඇල්ගොරිතම වෙත පැමිණෙමු.

  1. වත්මන් දර්ශකය 0 ලෙස ගබඩා කිරීම සඳහා නූල් s, අක්ෂර වර්ගයේ තොගයක් සහ විචල්‍යයක් ආරම්භ කරන්න.
  2. නූල් වල දිග වත්මන් දර්ශකයට සමාන නම්, තොගය හිස් 1 නම් 0 ආපසු එවන්න.
  3. නූල් වල වත්මන් දර්ශකයේ අක්‍ෂරය ආරම්භක වරහන් ද යන්න පරීක්ෂා කර, එය තොගයක් තුළට තල්ලු කර වත්මන් දර්ශකය + 1 ලෙස වත්මන් දර්ශකය සමඟ පුනරාවර්තන ඇමතුමක් ලබා දෙන්න.
  4. වෙනත් නම්, නූල් වල වත්මන් දර්ශකයේ අක්‍ෂරය සංවෘත වරහන් වේ නම්, තොගය හිස් ආපසු ඇත්දැයි පරීක්ෂා කරන්න. 0 වෙනත් නම්, තොගයේ ඉහළ කොටස ආරම්භක වරහනට සමාන නොවන්නේදැයි පරීක්ෂා කර බලන්න. ඉහළට ගොස් වත්මන් දර්ශකය + 0 ලෙස පුනරාවර්තන ඇමතුමක් ලබා දෙන්න.
  5. වෙනත් ආකාරයකින් නූල් වල වත්මන් දර්ශකයේ අක්ෂරය x ට සමාන නම්, පැරණි එකට සමාන තාවකාලික තොගයක් සාදා එය තුළට චරිතය තල්ලු කරන්න.
  6. විචල්ය res එකක් සාදන්න. වත්මන් දර්ශකය වත්මන් දර්ශකය + 1 සහ තාවකාලික සිරස් ලෙස පුනරාවර්තන ඇමතුමක් ගන්න. එහි ප්‍රති result ලය res හි ගබඩා කරන්න.
  7. Res 1 ට සමාන නම්, 1 ආපසු එවන්න.
  8. පැරණි තොගය හිස් නම්, 0 ආපසු දෙන්න.
  9. පැරණි තොගයේ සිට ඉහළට පොප් කර වත්මන් දර්ශකය සමඟ වත්මන් දර්ශකය + 1 සහ පැරණි තොගය ලෙස පුනරාවර්තන ඇමතුමක් ලබා දෙන්න.

ආදේශනය සමඟ සමබර ප්‍රකාශනය සඳහා C ++ වැඩසටහන

#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) අපි අමතර ඉඩ ප්‍රමාණයක් තොගයේ භාවිතා කළ නිසා.

ආශ්රිත