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


Ниво тешкоће Средњи
Често питани у амазонка Пешачење пророчанство Снапдеал Валмарт Лабс випро Иатра Зохо
Стацк низ

С обзиром на два низа с1 и с2 који представљају изразе који садрже оператор сабирања, оператор одузимања, мала слова и заграде. Проверите да ли су два израза у заградама иста.

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

Пример

Улазни 

с1 = "- (а + б + ц)"

с2 = "-абц"

Излаз 

да

Улазни 

с1 = "аб- (цд)"

с2 = "абцд"

Излаз

Не

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

  1. Иницијализујте два струне с1 и с2 представљају_изразе који садрже оператор сабирања, оператор одузимања, мале абецеде и заграде.
  2. Направите вектор и иницијализујте све вредности вектора као 0.
  3. Након тога створите стек логичког типа и у њега угурајте труе.
  4. Пређите низом 1 односно с1 и проверите да ли је знак у тренутном индексу у низу једнак '+' или '-', пређите на следећу итерацију.
  5. Иначе ако је знак у тренутном индексу у низу једнак отварајућој загради, проверите да ли знак у претходном индексу у низу није једнак '-', гурните вредност на врху стека у самом стеку гурните вредност не на врху стека у самом стеку.
  6. Ако 5 корака није потврдило, у супротном је ли знак на тренутном индексу у низу једнак затварачкој загради, искочите елемент на врху стека.
  7. Иначе проверите да ли стек има врх, ажурирајте вектор као в [с1 [и] - 'а'] + = (адјСигн (с1, и)? Адд? 1: -1: адд? -1: 1) иначе ажурирајте вектор као в [с1 [и] - 'а'] + = (адјСигн (с1, и)? адд? -1: 1: адд? 1: -1).
  8. Слично томе, поновите исте кораке са низом 2 тј. С2.
  9. Након тога пређите од 0 до 25 и проверите да ли вредност на тренутном индексу у вектору ако није једнака 0, исписати „Не“, а друго исписати „Да“.

Програм Ц ++ за проверу да ли су два израза са заградама иста

#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

Анализа сложености

Сложеност времена: О (мак (н1, н2)) где су н1 и н2 дужина задатих низова с1 односно с2.

Сложеност простора: О (мак (н1, н2)) јер смо користили простор за чување знакова задатих низова.

Референце