Mötərizəli iki ifadə eyni olub olmadığını yoxlayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Piyada çox yol qət eləmək Kahin Snapdeal Walmart Laboratoriyaları Wipro Yatra Zoho
Qalaq SimBaxılıb 43

Əlavə operatoru, çıxma operatoru, kiçik əlifbalar və mötərizəni ehtiva edən ifadələri əks etdirən iki s1 və s2 sətri verilmişdir. Mötərizəli iki ifadənin eyni olub olmadığını yoxlayın.

Mötərizəli iki ifadə eyni olub olmadığını yoxlayınPin

misal

Input 

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

s2 = “-abc”

Buraxılış 

bəli

Input 

s1 = “ab- (cd)”

s2 = “abcd”

Buraxılış

Yox

Mötərizəli iki ifadənin eyni olub olmadığını yoxlamaq üçün alqoritm

  1. İki başlayın strings əlavə operatoru, toplama işlemi operatoru, kiçik əlifbalar və mötərizəni ehtiva edən ifadələr təmsil edən s1 və s2.
  2. Bir vektor yaradın və vektorun bütün dəyərlərini 0 olaraq başlatın.
  3. Bundan sonra boole tipli bir yığın yaradın və içərisində doğru itələyin.
  4. 1, yəni s1 sətrindən keçin və sətirdəki cari indeksdəki simvolun '+' və ya '-' bərabər olduğunu yoxlayın, növbəti təkrarlanmaya gedin.
  5. Sətirdəki cari indeksdəki simvol açılış mötərizəyə bərabərdirsə, sətirdəki əvvəlki indeksdəki simvolun '-' -ya bərabər olmadığını yoxlayın, yığının üstündəki dəyəri yığının özündə itələyin. yığının özündəki yığının üstündəki dəyəri yox.
  6. Əgər 5 addım yoxlanılıbsa, başqa birində cərgədəki indeksdəki işarənin bağlanma mötərizəsinə bərabər olub olmadığını yoxlayınsa, elementi üst hissəyə yığın.
  7. Yığının üst olub olmadığını yoxlayın, vektoru v [s1 [i] - 'a'] + = (adjSign (s1, i)? Add? 1: -1: add? -1: 1) şəklində yeniləyin v [s1 [i] - 'a'] + = (adjSign (s1, i)? add? -1: 1: add? 1: -1) olaraq vektor.
  8. Eynilə, eyni addımları sətir 2 yəni s2 ilə təkrarlayın.
  9. Bundan sonra 0-dan 25-ə keçin və vektordakı cari indeksdəki dəyərin 0-a bərabər olmadığını yoxlayın, “Xeyr” yazdırın, əksinə “Bəli” yazdırın.

Mötərizəli iki ifadənin eyni olub olmadığını yoxlamaq üçün C ++ proqramı

#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

Mötərizəli iki ifadənin eyni olub olmadığını yoxlamaq üçün Java proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (max (n1, n2))) burada n1 və n2 müvafiq olaraq s1 və s2 sətirlərinin uzunluğudur.

Kosmik Mürəkkəblik: O (max (n1, n2))) çünki verilən simlərin simvollarını saxlamaq üçün yer istifadə etdik.

References

Translate »