იპოვნეთ დახურვის ფრჩხილის ინდექსი მოცემული გახსნის ფრჩხილისთვის გამოხატვაში


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Flipkart Oracle OYO ოთახები Snapdeal Walmart Labs Yatra
Array დასტის სიმებიანი

პრობლემის განცხადება

მოცემულია ა სიმებიანი s სიგრძის / ზომის n და მთელი რიცხვის მნიშვნელობა წარმოადგენს კვადრატული ფრჩხილის ინდექსს. გამოთქმაში იპოვნეთ მოცემული გახსნის ფრჩხილის დახურვის ფრჩხილის ინდექსი.

იპოვნეთ დახურვის ფრჩხილის ინდექსი მოცემული გახსნის ფრჩხილისთვის გამოხატვაში

მაგალითი

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

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

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

index = 0
-1

მიდგომა

გამოიყენეთ დასტის მონაცემთა სტრუქტურა მთელი რიცხვი ტიპი შეინახეთ გახსნის ფრჩხილების ინდექსი მოცემულ სტრიქონში. დაიწყეთ განმეორება მოცემულიდან სიმებიანი მოცემული ინდექსიდან დაწყებული. თუ გახსნის ფრჩხილი შეგხვდებათ, დააჭირეთ მას სტეკში. ყველა დახურვის ფრჩხილისთვის, რომელიც გახსნილია, სტეკიდან გახსენით ფრჩხილი. თუ სტეკი ცარიელი ხდება, ანუ სტეკის ზომა 0-ს გარკვეულ ინდექსში არის 1, დაბეჭდეთ ინდექსი. სხვა ბეჭდვა -XNUMX.

ალგორითმი

  1. სტრიქონის სიგრძის / ზომის ინიცირება n და მთელი რიცხვი, რომელიც წარმოადგენს გახსნის კვადრატული ფრჩხილის ინდექსს.
  2. მოცემული სტრიქონის შესაქმნელად გახსენით სამაგრის ინდექსის პოვნა, რომლითაც მოცემულია სტრიქონის მნიშვნელობა, რომელიც გამოხატავს გამოსახულებას და მთელი რიცხვი წარმოადგენს მოცემულ სტრიქონში გახსნის ფრჩხილის ინდექსს, რადგან ის არის პარამეტრი.
  3. შეამოწმეთ მოცემული ინდექსის სიმბოლო ტოლი არ არის გახსნის სამაგრის, ანუ '[', ბეჭდვა -1 და დაბრუნება.
  4. ამის შემდეგ შექმენით მთელი რიცხვის ტიპის დასტის მონაცემები სტრუქტურაში მოცემული სტრიქონის გახსნის ფრჩხილების ინდექსის შესანახად.
  5. მოცემული სტრიქონის გადაკვეთა დაწყებული მოცემული ინდექსიდან და შეამოწმეთ სიმბოლოში მიმდინარე ინდექსზე არსებული სიმბოლო ტოლია თუ არა გახსნის ფრჩხილის, დააჭირეთ / ჩასვით სიმბოლო სტეკში არსებულ სტრიქონში.
  6. სხვა, თუ სიმების მიმდინარე ინდექსში სიმბოლო ტოლია დახურვის ფრჩხილის, ანუ ']', ააფეთქეთ / ამოიღეთ ელემენტი დასტის ზედა ნაწილში. ამის შემდეგ, შეამოწმეთ არის თუ არა დასტა ცარიელი, ანუ სტეკის ზომა უდრის 0-ს, დაბეჭდეთ მიმდინარე ინდექსი და დააბრუნეთ.
  7. ბეჭდვა -1.

კოდი

C ++ პროგრამა, რომ იპოვოთ შესაბამისი დახურვის ფრჩხილი სამაგრის გასახსნელად

#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

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც n არის მოცემული სიმების სიგრძე s. მას შემდეგ, რაც ჩვენ გადავკვეთეთ სტრიქონში არსებული ყველა სიმბოლო, დროის სირთულე წრფივია.

სივრცის სირთულე

O (n) იმიტომ, რომ ჩვენ გამოვიყენეთ სივრცე მოცემული სიმების სიმბოლოების შესანახად. სივრცის სირთულე დამოკიდებულია ფრჩხილების რაოდენობაზე. მაგრამ უარეს შემთხვევაში, ყველა სიმბოლო შეიძლება იყოს კვადრატული ფრჩხილები. ამრიგად, სივრცის სირთულე ასევე ხაზოვანია.

ლიტერატურა