Βρείτε ευρετήριο κλεισίματος βραχίονα για δεδομένο άνοιγμα βραχίονα σε μια έκφραση


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα Flipkart μαντείο Δωμάτια OYO Snapdeal Εργαστήρια Walmart Yatra
Παράταξη Στοίβα κορδόνι

Δήλωση προβλήματος

Δεδομένου α κορδόνι s μήκους / μεγέθους n και ακέραια τιμή που αντιπροσωπεύει το ευρετήριο ενός ανοιγόμενου τετραγωνικού βραχίονα. Βρείτε δείκτη βραχίονα κλεισίματος για ένα δεδομένο βραχίονα ανοίγματος σε μια έκφραση.

Βρείτε ευρετήριο κλεισίματος βραχίονα για δεδομένο άνοιγμα βραχίονα σε μια έκφραση

Παράδειγμα

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.

Κώδικας

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

Πρόγραμμα Java για εύρεση αντίστοιχου βραχίονα κλεισίματος για άνοιγμα βραχίονα

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) επειδή χρησιμοποιήσαμε χώρο για να αποθηκεύσουμε τους χαρακτήρες της δεδομένης συμβολοσειράς. Η πολυπλοκότητα του χώρου εξαρτάται από τον αριθμό των αγκυλών. Αλλά στη χειρότερη περίπτωση, όλοι οι χαρακτήρες μπορεί να είναι αγκύλες. Έτσι, η διαστημική πολυπλοκότητα είναι επίσης γραμμική.

αναφορές