Bir ifadənin cüt parantezə sahib olub olmadığını tapın

Verilmiş a sim balanslaşdırılmış mötərizə ehtiva edir. İfadənin / sətrin cüt mötərizə içərisində olub olmadığını tapın.

Parentezi təkrarlayın

Bir ifadə eyni tarazlı mötərizənin ortasında və ya əhatəsində olduqda, yəni eyni açma və bağlama mötərizəsi arasında bir dəfədən çox çəkildiyi deyilir. Məsələn - ((a + b)) yəni bütün ifadə iki oxşar mötərizənin ortasındadır, lakin (a + (b)) ifadəsində nə bütün ifadə, nə də hər hansı bir alt ifadədə cüt mötərizə yoxdur.

Məsələn -

Pin

misal

Input: s = “(((a + (b)) + (c + d)))”

Çıxış: İfadədə cüt mötərizə var.

Input: s = “((a + b) + c + d)”

Çıxış: İfadədə cüt mötərizə yoxdur.

Yığından istifadə üsulu

Bir yığın yaradın. Verilən simdən keçin və ya təkrarlayın. Hər bir işarəni yoxlayın, əgər '(' və ya hər hansı bir operatora və ya operanda bərabərdirsə, onu yığına itələyin. Başqa '' -ya bərabərdirsə ''), eyni tipli açıq mötərizəyə qədər simvolları açın. Bir sayma dəyişkəni istifadə olunur, açılış mötərizəsinə qədər hər bir simvol üçün artırın '(' tapıldı. Dəyişən sayı 1-dən azdırsa, əks halda təkrarlanan mötərizə tapılmadı.

Alqoritm

1. Balanslaşdırılmış mötərizəni ehtiva edən bir simli ifadəni başlatın.
2. Başlanğıc a qalaq simvol saxlamaq üçün.
3. Sətri keçin və cari simvolun yekun mötərizə olmadığını yoxlayın, xarakteri yığına itələyin.
4. Başqa biri yığının üst hissəsini açın və mötərizənin içərisindəki elementləri 0 kimi saymaq üçün sayğacı başladın. Üstü açılış mötərizəsinə bərabər deyilsə, sayğacı artırın və üst hissəsini açın.
5. İçindəki elementlərin 1-dən az olub olmadığını yoxlayın, 1-i qaytarın.
6. Saxta qayıdın.

İfadə üçün C ++ Proqramının Parantezi Yoxdur, Yoxdur

#include <bits/stdc++.h> 
using namespace std; 
  
bool isDuplicate(string s){ 
    
    stack<char> Stack; 
  
    for(char ch : s){ 
        
        if(ch == ')'){ 
            
            char top = Stack.top(); 
            Stack.pop(); 
  
            int elementsInside = 0; 
            
            while(top != '('){ 
                elementsInside++; 
                top = Stack.top(); 
                Stack.pop(); 
            } 
            
            if(elementsInside < 1){ 
                return 1; 
            } 
        } 
  
        else{
            Stack.push(ch); 
        }    
    } 
  
    return false; 
} 
  
  
int main(){ 
    
    string s = "(((a+(b))+(c+d)))"; 
  
    if(isDuplicate(s)){ 
        cout<<"Expression contains duplicate parenthesis.";
    }    
    else{
        cout<<"Expression does not contain duplicate parenthesis."; 
    }    
  
    return 0; 
}

Expression contains duplicate parenthesis.

İfadə üçün Java Proqramının Parentezi Yoxdur, Olmaz

import java.util.Stack; 
  
class Parenthesis{ 
  
    static boolean isDuplicate(String s){ 
        
        Stack<Character> Stack = new Stack<>(); 
  
        char[] str = s.toCharArray(); 
        for(char ch : str) { 
            
            if (ch == ')') { 
                
                char top = Stack.peek(); 
                Stack.pop(); 
  
                int elementsInside = 0; 
                
                while (top != '(') { 
                    elementsInside++; 
                    top = Stack.peek(); 
                    Stack.pop(); 
                } 
                
                if (elementsInside < 1){ 
                    return true; 
                } 
            } 
            
            else{ 
                Stack.push(ch); 
            } 
        } 
  
        return false; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "(((a+(b))+(c+d)))"; 
  
        if(isDuplicate(s)){ 
            System.out.println("Expression contains duplicate parenthesis."); 
        } 
        
        else{ 
            System.out.println("Expression does not contain duplicate parenthesis."); 
        } 
  
    } 
}

Expression contains duplicate parenthesis.

İfadə üçün Mürəkkəblik Analizi cüt parantezə malikdir və ya yoxdur

Zamanın mürəkkəbliyi: O (n), burada n ifadədəki simvol sayıdır.

Köməkçi məkan: O (n), çünki simvolları saxlamaq üçün yığın boşluğundan istifadə etdik.

References