Bir simli iç içə parantezin maksimum dərinliyini tapın

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Bir s s verilmişdir. Verilən iç içə mötərizənin maksimum dərinliyini yazdırmaq üçün kodu yazın sim.

Mündəricat

misal

Giriş: s = "(a (b) (c) (d (e (f) g) h) I (j (k) l) m)")

Çıxış: 4

Giriş: s = "(p ((q)) ((s) t))"

Çıxış: 3

Stack istifadə

Alqoritm

N uzunluğunda bir s sətir başlayın.
Bir yaradın qalaq maksimum dəyəri və cari maksimum dəyərini saxlamaq və dəyərlərini 0 olaraq təyin etmək üçün parantezi və iki dəyişəni saxlamaq.
Sətrdən keçin və cari simvolun açılış mötərizəsi olub olmadığını yoxlayın, yığına itələyin və cari maksimum dəyəri artırın. Cari maksimum dəyər maksimum dəyərdən böyükdürsə, maksimum dəyəri cari maksimum dəyər kimi yeniləyin.
Başqa bir cari xarakter bağlanma mötərizəsidirsə, yığının üst simvolunu açın. Cari maksimum dəyərin 0-dan böyük olduğunu və açılan simvolun açılış mötərizəsi olub olmadığını yoxlayın, cari maksimum dəyəri başqa return -1 -ə endirin.
Yığın boş deyilsə, -1-ə qayıdın.
Başqa bir şey maksimum dəyəri qaytarır.

C ++ Proqramı bir sətirdə iç içə mötərizənin maksimum dərinliyini tapmaq

#include <bits/stdc++.h> 
using namespace std; 

class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        char* array;  
};  
  
Stack* createStack(unsigned capacity){  
    Stack* stack = new Stack(); 
    stack->capacity = capacity;  
    stack->top = -1;  
    stack->array = new char[(stack->capacity * sizeof(char))];  
    return stack;  
}  
  
int isFull(Stack* stack){ 
    return stack->top == stack->capacity - 1; 
}  
  
int isEmpty(Stack* stack){ 
    return stack->top == -1;
}  
  
void push(Stack* stack, char item){  
    if(isFull(stack))  
        return;  
    stack->array[++stack->top] = item;  
}  
  
char pop(Stack* stack){  
    if(isEmpty(stack))  
        return -1;  
    return stack->array[stack->top--];  
}  

int maxDepth(string s){ 
    int n = s.length();  
    Stack* stack = createStack(n);
    int current_max = 0; 
    int max = 0;   
  
    for(int i = 0; i<n; i++){
        
        if(s[i] == '('){ 
            push(stack, s[i]);
            current_max++; 
  
            if(current_max > max){ 
                max = current_max;
            }    
        } 
        
        else if(s[i] == ')'){ 
            char c = pop(stack);
            if((current_max > 0) && (c == '(')){ 
                current_max--; 
            }    
            else{
                return -1;
            }    
        } 
    } 
  
    if(!isEmpty(stack)){ 
        return -1; 
    }    
  
    return max; 
} 
  
int main(){
    
    string s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
    cout<<maxDepth(s); 
    
    return 0; 
}

Bir simli iç içə mötərizənin maksimum dərinliyini tapmaq üçün Java Proqramı

import java.util.*; 
  
class Stack{ 
    int size; 
    int top; 
    char[] a;  
  
    boolean isEmpty(){ 
        return(top < 0); 
    } 
      
    Stack(int n){ 
        top = -1; 
        size = n; 
        a = new char[size]; 
    } 
  
    boolean push(char x){ 
        if (top >= size){ 
            System.out.println("Stack Overflow"); 
            return false; 
        } 
        else{ 
            a[++top] = x; 
            return true; 
        } 
    } 
  
    char pop(){ 
        if(top < 0){ 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else{ 
            char x = a[top--]; 
            return x; 
        } 
    } 
}

class Depth{
    
    static int maxDepth(String s){
        
        int current_max = 0;
        int max = 0; 
        int n = s.length(); 
        Stack stack = new Stack(n);
  
        for(int i = 0; i < n; i++){ 
            if(s.charAt(i) == '('){ 
                current_max++; 
                stack.push(s.charAt(i));
  
                if(current_max > max){ 
                    max = current_max; 
                } 
            } 
            else if(s.charAt(i) == ')'){ 
                
                char c = stack.pop();
                
                if((current_max > 0) && (c == '(')){ 
                    current_max--; 
                } 
                else{ 
                    return -1; 
                } 
            } 
        } 
  
        if(!stack.isEmpty()){ 
            return -1; 
        } 
  
        return max; 
    } 
  
    public static void main(String[] args){
        
        String s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
        System.out.println(maxDepth(s)); 
        
    } 
}

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n simin ölçüsüdür.

Köməkçi məkan: O (n), çünki n işarəsini saxlamaq üçün yığında yer istifadə etdik.

Stack istifadə etmədən