Пронађите израз израза у закључној загради за дати отвор у загради


Ниво тешкоће Лако
Често питани у адобе амазонка Флипкарт пророчанство ОИО собе Снапдеал Валмарт Лабс Иатра
Ред Стацк низ

Изјава о проблему

С обзиром на а низ с дужине / величине н и целобројна вредност која представља индекс почетне квадратне заграде. Пронађи индекс закључне заграде за дату отварајућу заграду у изразу.

Пронађите израз израза у закључној загради за дати отвор у загради

Пример

s = "[ABC[23]][89]"

index = 0
8
s = "[C-[D]]"

index = 3
5
s = "E-[FX]]"

index = 0
-1

Приступ

Коришћење стек структура података о цео број типе за чување индекса почетних заграда у датом низу. Започните итерацију кроз дато низ полазећи од датог индекса. Ако се нађе отворни носач, гурните га у стог. За сваки закључни заграда који се нађе извуците отворни заграда из стека. Ако стек постане празан, тј. Величина стога је 0 на неком индексу, одштампајте индекс. Елсе принт -1.

Алгоритам

  1. Иницијализујте низ с дужине / величине n и целу вредност која представља индекс почетне углате заграде.
  2. Створите функцију за проналажење индекса затварајућих заграда за задати заградни отвор у датом низу који прихвата вредност низа која представља израз и целобројну вредност која представља индекс отворне заграде у датом низу као свој параметар.
  3. Проверите да ли знак са датим индексом није једнак отворној загради, тј. [[', Испис -1 и повратак.
  4. Након тога креирајте структуру података стека целобројног типа да би у њу смештали индекс почетних заграда датог низа.
  5. Пређите кроз дати низ почевши од датог индекса и проверите да ли је знак у тренутном индексу у низу једнак почетној загради, притисните / уметните знак у тренутном индексу у низу у низу.
  6. Иначе ако је знак у тренутном индексу у низу једнак затварачу, тј.]], Искочите / уклоните елемент на врху стека. Након тога проверите да ли је стек празан, односно величина стека једнака 0, одштампајте тренутни индекс и вратите.
  7. Одштампај -1.

код

Програм Ц ++ за проналажење одговарајуће заграде за отварање заграде

#include <bits/stdc++.h> 
using namespace std; 
  
void test(string expression, int index){ 
    int i; 
      
    if(expression[index]!='['){ 
        cout << "-1\n"; 
        return; 
    } 
      
    stack <int> st; 
      
    for(i = index; i < expression.length(); i++){ 
          
        if(expression[i] == '['){ 
            st.push(expression[i]);
        }
          
        else if(expression[i] == ']'){ 
            st.pop(); 
            if(st.empty()){ 
                cout << i << "\n"; 
                return; 
            } 
        } 
    } 
      
    cout << "-1\n"; 
} 
  
int main() { 
    string s = "[ABC[23]][89]";
    int index = 0;
    
    test(s, index); 
    
    return 0; 
}
8

Јава програм за проналажење одговарајуће заграде за отварање заграде

import java.util.Stack; 

class FindIndex{ 
  
    static void test(String expression, int index){ 
        int i; 
  
        if(expression.charAt(index) != '['){ 
            System.out.print("-1\n"); 
            return; 
        } 
  
        Stack<Integer> st = new Stack<>(); 
  
        for(i = index; i < expression.length(); i++){ 
  
            if(expression.charAt(i) == '['){ 
                st.push((int) expression.charAt(i)); 
            } 
            
            else if(expression.charAt(i) == ']'){ 
                st.pop(); 
                if(st.empty()){ 
                    System.out.print( i ); 
                    return; 
                } 
            } 
        } 
  
        System.out.print("-1\n"); 
    } 
  
    public static void main(String[] args){
        String s = "[ABC[23]][89]";
        int index = 0;
        
        test(s, index); 
    } 
}
8

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

Сложеност времена

О (н) где је н дужина датог низа с. Пошто смо прешли преко свих знакова доступних у низу, временска сложеност је линеарна.

Сложеност простора

О (н) јер смо користили размак за чување знакова датог низа. Сложеност простора зависи од броја заграда. Али у најгорем случају, сви знакови могу бити углате заграде. Стога је сложеност простора такође линеарна.

Референце