ביטוי מאוזן עם החלפה


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית טיול אורקל Snapchat Snapdeal מעבדות וולמארט Wipro יטרה Zoho
לערום מחרוזת

בבעיה מאוזנת עם החלפה נתנו מחרוזת המכילה סוגריים כלומר '(', ')', '[', ']', '{', '}'. ה מחרוזת מכיל גם x במקומות מסוימים כתחליף לסוגריים. בדוק אם ניתן להמיר את המחרוזת לביטוי עם סוגריים תקפים לאחר שהחלפת את כל ה- x בסוגריים כלשהם.

ביטוי מאוזן עם החלפה

דוגמה

קֶלֶט 

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

תְפוּקָה

 יש

קֶלֶט

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

תְפוּקָה 

לא

אַלגוֹרִיתְם

כעת אנו יודעים את הצהרת הבעיה של בעיה מאוזנת עם החלפה. אז, אנו מגיעים לאלגוריתם שלהלן לפתרון.

  1. אתחל מחרוזות, ערימה של סוג תו ומשתנה כדי לאחסן את האינדקס הנוכחי כ- 0.
  2. אם אורך המחרוזת שווה למדד הנוכחי, החזר 1 אם הערימה ריקה אחרת 0.
  3. בדוק אם התו באינדקס הנוכחי במחרוזת הוא סוגריים פותחים, דחף אותו לערימה והחזיר שיחה רקורסיבית עם האינדקס הנוכחי כאינדקס הנוכחי + 1.
  4. אחרת אם תו באינדקס הנוכחי במחרוזת הוא סוגר סוגר, בדוק אם הערימה ריקה החזר 0 אחר בדוק אם החלק העליון של הערימה אינו שווה לסוגריים הפותחים לדמות הנוכחית במחרוזת, החזר 0. הקפץ את למעלה והחזר שיחה רקורסיבית עם האינדקס הנוכחי כאינדקס הנוכחי + 1.
  5. אחרת אם התו באינדקס הנוכחי במחרוזת שווה ל- x, צור ערימה זמנית השווה לזה הישן ודחף את התו לתוכו.
  6. צור מילוי משתנה. בצע שיחה רקורסיבית עם האינדקס הנוכחי כאינדקס הנוכחי + 1 וערימה זמנית. אחסן את התוצאה במילואים.
  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

תוכנית Java לביטוי מאוזן עם החלפה

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 שטח נוסף בערימה.

הפניות