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


Ниво тешкоће Лако
Често питани у амазонка Пешачење пророчанство Снапдеал Валмарт Лабс випро Иатра Зохо
Стацк низ

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

На пример -

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

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

Пример

Улаз: с = “[()] {} {[() ()] ()}”

Излаз: Израз је уравнотежен.

Улаз: с = “[() {}”

Излаз: Израз није уравнотежен.

Метод

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

Алгоритам

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

Ц ++ програм за проверу уравнотежених заграда у изразу

#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.

Јава програм за проверу уравнотежених заграда у изразу

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.

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

Сложеност времена: О (н) где је н број заграда / знакова у датом низу.

Помоћни простор: О (н) где је н број заграда / знакова у датом низу, јер смо овде користили простор за складиштење н знакова у стеку.

Референце