Проверете дали два израза со загради се исти


Ниво на тешкотија Медиум
Често прашувано во Амазон Крстоносните Oracle Snapdeal Лаборатории Walmart Випро Yatra 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)? Add? 1: -1: add? -1: 1) друго ажурирајте го вектор како v [s1 [i] - 'a'] + = (adjSign (s1, i)? add? -1: 1: add? 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

Јава програма за да провери дали два израза со загради се исти

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)) затоа што користевме простор за складирање на знаците на дадените низи.

Референци