בדוק אם שני ביטויים עם סוגריים זהים


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

ניתן שתי מחרוזות s1 ו- s2 המייצגות ביטויים המכילים אופרטור חיבור, אופרטור חיסור, אלפבית קטן, וסוגריים. בדוק אם שני ביטויים עם סוגריים זהים.

בדוק אם שני ביטויים עם סוגריים זהים

דוגמה

קֶלֶט 

s1 = “- (a + b + c)”

s2 = “-abc”

תְפוּקָה 

יש

קֶלֶט 

s1 = “ab- (cd)”

s2 = "abcd"

תְפוּקָה

לא

אלגוריתם לבדוק אם שני ביטויים עם סוגריים זהים

  1. אתחל שתיים מחרוזות s1 ו- s2 המייצגים ביטויים המכילים אופרטור תוספת, מפעיל חיסור, אלפבית קטן, וסוגריים.
  2. צור וקטור ואתחל את כל ערכי הווקטור כ- 0.
  3. לאחר מכן צור ערימה מסוג בוליאני ודחף בה אמת.
  4. חצה דרך המחרוזת 1 כלומר s1 ובדוק אם התו באינדקס הנוכחי במחרוזת שווה ל- '+' או '-', עבור לאיטרציה הבאה.
  5. אחרת אם התו באינדקס הנוכחי במחרוזת שווה לסוגריים פותחים, בדוק אם התו באינדקס הקודם במחרוזת אינו שווה ל- '-', דחף את הערך בראש הערימה בערימה עצמה אחרת דחף את הערך לא בחלק העליון של הערימה בערימה עצמה.
  6. אם שלב 5 לא בדק אז אחר אם התו באינדקס הנוכחי במחרוזת שווה לסוגריים סוגרים, הקפץ את האלמנט בראש הערימה.
  7. עוד בדוק אם הערימה כוללת את החלק העליון, עדכן את הווקטור כ- v [s1 [i] - 'a'] + = (adjSign (s1, i)? הוסף? 1: -1: הוסף? -1: 1) אחרת עדכן את וקטור כמו v [s1 [i] - 'a'] + = (adjSign (s1, i)? הוסף? -1: 1: הוסף? 1: -1).
  8. באופן דומה, חזור על אותם שלבים עם מחרוזת 2 כלומר s2.
  9. לאחר מכן חצו בין 0 ל -25 ובדקו אם הערך באינדקס הנוכחי בווקטור אם אינו שווה ל- 0, הדפיסו "לא" אחרת הדפיסו "כן".

תוכנית C ++ כדי לבדוק אם שני ביטויים עם סוגריים זהים

#include <bits/stdc++.h> 
using namespace std; 
  
const int MAX_CHAR = 26; 
  
bool adjSign(string s, int i){ 
    if(i == 0){ 
        return true;
    }
    
    if(s[i - 1] == '-'){ 
        return false; 
    }
    
    return true; 
}; 
  
void eval(string s, vector<int>& v, bool add){ 
    stack<bool> stk; 
    stk.push(true); 
  
    int i = 0; 
    while(s[i] != '\0'){ 
        if(s[i] == '+' || s[i] == '-'){ 
            i++; 
            continue; 
        } 
        
        if(s[i] == '('){ 
            if(adjSign(s, i)){  
                stk.push(stk.top());
            }
            else{ 
                stk.push(!stk.top()); 
            }
        } 
  
        else if(s[i] == ')'){  
            stk.pop(); 
        }
          
        else{ 
            if(stk.top()){                  
                v[s[i] - 'a'] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); 
            }
  
            else{                 
                v[s[i] - 'a'] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); 
            }
        } 
        i++; 
    } 
}; 
  
bool areSame(string s1, string s2){ 
    vector<int> v(MAX_CHAR, 0); 
  
    eval(s1, v, true); 
  
    eval(s2, v, false); 
  
    for(int i = 0; i < MAX_CHAR; i++){ 
        if(v[i] != 0){  
            return false;
        }
    }
  
    return true; 
} 
  
int main(){ 
    string s1 = "-(a+b+c)", s2 = "-a-b-c"; 
    
    if(areSame(s1, s2)){ 
        cout << "Yes\n"; 
    }
    else{
        cout << "No\n"; 
    }
    
    return 0; 
}
Yes

תוכנית Java כדי לבדוק אם שני ביטויים עם סוגריים זהים

import java.io.*; 
import java.util.*; 
  
class CheckExpressions{ 
  
    static final int MAX_CHAR = 26; 
  
    static boolean adjSign(String s, int i){ 
        if(i == 0){ 
            return true;
        }
        
        if(s.charAt(i - 1) == '-'){ 
            return false; 
        }
        
        return true; 
    }; 
  
    static void eval(String s, int[] v, boolean add){ 
  
        Stack<Boolean> stk = new Stack<>(); 
        stk.push(true); 
  
        int i = 0; 
        while(i < s.length()){ 
            if(s.charAt(i) == '+' || s.charAt(i) == '-'){ 
                i++; 
                continue; 
            } 
            
            if(s.charAt(i) == '('){ 
                if(adjSign(s, i)){ 
                    stk.push(stk.peek());
                }
                
                else{
                    stk.push(!stk.peek()); 
                }
            } 
  
            else if(s.charAt(i) == ')'){ 
                stk.pop(); 
            }
  
            else{ 
                if(stk.peek()){ 
                    v[s.charAt(i) - 'a'] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); 
                }
  
                else{
                    v[s.charAt(i) - 'a'] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); 
                }
            } 
            i++; 
        } 
    }; 
  
    static boolean areSame(String s1, String s2){ 
  
        int[] v = new int[MAX_CHAR]; 
  
        eval(s1, v, true); 
  
        eval(s2, v, false); 
  
        for(int i = 0; i < MAX_CHAR; i++){ 
            if(v[i] != 0){ 
                return false; 
            }
        }
  
        return true; 
    } 
  
    public static void main(String[] args){ 
  
        String s1 = "-(a+b+c)", s2 = "-a-b-c"; 
        
        if(areSame(s1, s2)){ 
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    } 
}
Yes

ניתוח מורכבות

מורכבות זמן: O (מקסימום (n1, n2)) כאשר n1 ו- n2 הם אורך המיתרים הנתונים s1 ו- s2 בהתאמה.

מורכבות שטח: O (מקסימום (n1, n2)) כי השתמשנו ברווח לאחסון הדמויות של המחרוזות הנתונות.

הפניות