Ə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ündəricat
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
- İ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.
- Bir vektor yaradın və vektorun bütün dəyərlərini 0 olaraq başlatın.
- Bundan sonra boole tipli bir yığın yaradın və içərisində doğru itələyin.
- 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.
- 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.
- Ə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.
- 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.
- Eynilə, eyni addımları sətir 2 yəni s2 ilə təkrarlayın.
- 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.
