식에서 균형 잡힌 괄호 확인

난이도 쉽게
자주 묻는 질문 아마존 인상 신탁 스냅 딜 월마트 연구소 위 프로 야 트라 조호 (Zoho)
스택 조회수 27

주어진 길이 n의 s. 모든 여는 괄호에 닫는 괄호가 있는지 확인하십시오. 즉, 모든 괄호가 균형을 이루고 있는지 확인하십시오. 즉, 모든 '{', '('및 '['에 대해 각각 '}', ')'및 ']'가 있으면 표현식이 균형을 이룬다 고 말할 수도 있습니다.

예를 들어 –

"{[()]}"표현식은 여는 괄호에 대해 일종의 닫는 괄호가 있기 때문에 균형 잡힌 괄호를 포함합니다.

식에서 균형 잡힌 괄호 확인

입력: s =“[()] {} {[() ()] ()}”

출력: 표정이 균형을 이룹니다.

입력: s =“[() {}”

출력: 표현이 균형을 이루지 않습니다.

방법

먼저 스택을 생성합니다. 각 문자에 대해 여는 괄호 (예 : '{', '('또는 '['))인지 확인하고 해당 문자를 스택에 넣습니다. 그렇지 않으면 닫는 괄호 (예 : '}', ')'또는 ']) ', 스택의 맨 위가 비슷한 종류의 괄호를 열고 있는지 확인하고 스택에서 꺼내고 다음 문자에 대한 루프를 계속합니다. 그렇지 않으면 false를 반환합니다. Stack이 끝에 비어 있으면 표현식에 균형 잡힌 괄호가 포함되어 있고 그렇지 않으면 괄호가 균형이 맞지 않음을 의미합니다.

암호알고리즘

  1. 길이가 n 인 문자열 s를 초기화합니다.
  2. 만들기 스택 문자를 저장합니다.
  3. 문자열을 가로 질러 현재 문자가 여는 괄호인지 확인하고 스택에 밀어 넣고 계속합니다.
  4. 스택이 비어 있으면 false를 반환합니다.
  5. 닫는 괄호를 전환하고 스택 맨 위에있는 문자가 여는 괄호인지 확인하고 닫는 괄호와 동일한 유형인지 확인하고 맨 위 문자를 팝하고 끊습니다. 그렇지 않으면 false를 반환합니다.
  6. 스택이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

식에서 균형 잡힌 괄호를 확인하는 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 개의 문자를 저장하기 위해 공백을 사용했기 때문입니다.

참조

Translate »