Проверете дали се израмнети загради во изразот


Ниво на тешкотија Лесно
Често прашувано во Амазон Крстоносните Oracle Snapdeal Лаборатории Walmart Випро Yatra Zoho
Магацинот Стринг

Со оглед на низа s со должина n. Проверете дали има заграда за затворање за секоја заграда за отворање, т.е. дали сите загради се избалансирани. Со други зборови, можеме исто така да кажеме дека, ако имаме "}", ")" и "]" за секое "{", "(" и "[" соодветно, изразот се вели дека е избалансиран.

На пример -

Изразот „{[()]}“ содржи балансирани загради затоа што има некаква затворачка заграда за заграда на отворање.

Проверете дали се израмнети загради во изразот

пример

влез: s = "[()] {} {[() ()] ()}"

излез: Изразот е избалансиран.

влез: s = „[() {}“

излез: Изразот не е балансиран.

Метод

Прво, создаваме оџак. За секој знак проверете дали е тоа заграда на отворање, т.е. или '{', '(' или '[', притиснете го знакот во оџакот. Друго ако е заграда на затворање, т.е. или '}', ')' или '] ', проверете дали горниот дел од оџакот отвора загради од сличен вид, појавувајте го од оџакот и продолжете ја јамката за следните знаци. Друго се врати лажно. Ако Стак е празен на крајот, тоа значи дека изразот содржи балансирани загради, инаку заградите не се балансирани.

Алгоритам

  1. Иницијализира низа со должина n.
  2. Креирај магацинот за чување на ликовите.
  3. Поминете низ низата и проверете дали тековниот карактер е заграда на отворање, турнете го во оџакот и продолжете.
  4. Ако оџакот е празен, вратете неточно.
  5. Префрлете ја заградата за затворање и проверете дали карактерот на горниот дел од оџакот е заградата за отворање од ист тип како заградата за затворање да се појави горниот карактер и да се пробие. Друго се врати лажно.
  6. Ако оџакот е празен, вратете е точно, друго вратете неточно.

Програма C ++ за проверка на избалансирани загради во израз

#include<bits/stdc++.h> 
using namespace std; 
  
bool isBalanced(string str){ 
    stack<char> s; 
    char x; 
  
    for(int i=0; i<str.length(); i++){ 
        if(str[i]=='('||str[i]=='['||str[i]=='{'){ 
            s.push(str[i]); 
            continue; 
        }
  
        if(s.empty()) 
           return false; 
  
        switch(str[i]){ 
            case ')': 
      
                x = s.top(); 
                s.pop(); 
                if(x=='{' || x=='[') 
                    return false; 
                break; 
      
            case '}': 
      
                x = s.top(); 
                s.pop(); 
                if(x=='(' || x=='[') 
                    return false; 
                break; 
      
            case ']': 
      
                x = s.top(); 
                s.pop(); 
                if(x =='(' || x == '{') 
                    return false; 
                break; 
        } 
    } 
  
    return (s.empty()); 
} 
  
int main(){ 
    string s = "[()]{}{[()()]()}"; 
  
    if(isBalanced(s)){ 
        cout<<"Expression is balanced."; 
    }    
    else{
        cout<<"Expression is not balanced."; 
    }    
    return 0; 
}
Expression is balanced.

Java програма за проверка на избалансирани загради во израз

class Parantheses{ 
    
    static class stack{ 
        int top=-1; 
        char items[] = new char[100]; 
        
        void push(char x){ 
            if(top == 99){ 
                System.out.println("Stack full"); 
            }  
            
            else{ 
                items[++top] = x; 
            } 
        } 
    
        char pop(){ 
            if(top == -1){ 
                System.out.println("Underflow error"); 
                return '\0'; 
            }  
            
            else{ 
                char element = items[top]; 
                top--; 
                return element; 
            } 
        } 
    
        boolean isEmpty(){ 
            return (top == -1) ? true : false; 
        } 
    } 
    
    static boolean isPair(char character1, char character2){ 
        if(character1 == '(' && character2 == ')') 
            return true; 
        
        else if(character1 == '{' && character2 == '}') 
            return true; 
        
        else if(character1 == '[' && character2 == ']') 
            return true; 
        
        else
            return false; 
    } 
    
    static boolean isBalanced(char s[]){ 
        stack st=new stack(); 
        
        for(int i=0;i<s.length;i++){ 
        
            if(s[i] == '{' || s[i] == '(' || s[i] == '[') 
                st.push(s[i]); 
            
            if(s[i] == '}' || s[i] == ')' || s[i] == ']'){ 
            
                if (st.isEmpty()){ 
                    return false; 
                }  
                
                else if( !isPair(st.pop(), s[i])){ 
                    return false; 
                } 
            } 
        
        } 
        
        if(st.isEmpty()) 
            return true;
            
        else
            return false; 
    }  
    
    public static void main(String[] args){ 
        char s[] = {'[','(',')',']','{','}','{','[','(',')','(',')',']','(',')','}'}; 
        
        if(isBalanced(s)){ 
            System.out.println("Expression is balanced.");
        }    
        
        else{
            System.out.println("Expression is not balanced.");   
        }
    } 
}
Expression is balanced.

Анализа на сложеност за избалансирани загради во израз

Временска комплексност: O (n) каде n е бројот на загради / знаци во дадената низа.

Помошен простор: O (n) каде n е бројот на загради / знаци во дадената низа затоа што тука користевме простор за складирање на n карактери во оџакот.

Референци