식에 중복 대괄호가 포함되어 있는지 여부


난이도 중급
자주 묻는 질문 아마존 Paytm
스택

주어진 연산자, 피연산자 및 괄호의 표현식을 포함하는 s. 주어진 문자열에 불필요한 괄호가 포함되어 있지 않으면 표현식이 여전히 동일한 결과를 제공하는지 찾습니다. 즉, 표현식에 중복 대괄호가 포함되어 있는지 여부를 찾아야합니다.

중복 브래킷

표현식 또는 하위 표현식이 불필요하거나 여러 개의 괄호로 둘러싸여 있어도 표현식이 동일한 결과를 제공하는 경우 이러한 괄호를 중복 괄호라고합니다.

예 :

string s = "(a + (b) / c)"로 지정합니다.

여기서 주어진 문자열은 (a + b / c)로 쓸 수 있으며 여전히 동일한 의미를 나타냅니다. 따라서 주어진 문자열 s = "(a + (b) / c)"에 중복 대괄호가 포함되어 있다고 말할 수 있습니다.

식에 중복 대괄호가 포함되어 있는지 여부

입력 : s =“((a + b))”

출력 : 가능

입력 : s =“(a + b * (cd))”

출력 : 아니

표현식에 중복 대괄호가 포함되어 있는지 여부를 찾기위한 알고리즘

  1. 연산자, 피연산자 및 괄호 표현식이 포함 된 문자열 s를 초기화합니다.
  2. 만들기 스택 데이터 구조.
  3. 주어진 문자열을 순회하여 문자열의 현재 인덱스에있는 문자가 ')'와 같지 않은지 확인하고 스택에있는 문자열의 현재 인덱스에있는 문자를 푸시합니다.
  4. 그렇지 않으면 문자 유형의 가변 상단을 만들고 스택 상단에 요소를 저장하고 스택 상단을 팝합니다.
  5. 부울 유형의 변수 플래그를 만들고 true로 초기화합니다.
  6. 변수 top이 '('와 같지 않을 때 트래버스하고 변수 top이 '+', '-', '*'또는 '/'와 같은지 확인하고 부울 변수 플래그의 값을 false로 업데이트합니다.
  7. 변수 상단의 스택 상단에 요소를 저장하고 스택 상단을 팝합니다.
  8. 부울 변수 플래그의 값이 true인지 확인하고 true를 반환합니다.
  9. 거짓을 반환합니다.
  10. 반환 된 값이 true이면 "Yes"를 인쇄하고 그렇지 않으면 "No"를 인쇄합니다.

식을 찾기위한 C ++ 프로그램에 중복 대괄호가 포함되어 있는지 여부

#include <bits/stdc++.h> 
using namespace std; 
  
bool checkRedundancy(string& s){ 
    stack<char> st; 
  
    for(auto& ch : s){ 
        if(ch == ')'){ 
            char top = st.top(); 
            st.pop(); 
  
            bool flag = true; 
  
            while(top != '('){ 
                if(top == '+' || top == '-' || top == '*' || top == '/'){ 
                    flag = false; 
                }
  
                top = st.top(); 
                st.pop(); 
            } 
  
            if(flag == true){ 
                return true; 
            }
        } 
        else{
            st.push(ch); 
        }
    } 
    return false; 
} 
  
void findRedundant(string& s){ 
    bool ans = checkRedundancy(s); 
    if(ans == true){ 
        cout << "Yes\n";
    }
    else{
        cout << "No\n"; 
    }
} 
  
int main(){
    
    string s = "((a+b))"; 
    findRedundant(s); 
  
    return 0; 
}
Yes

표현식을 찾기위한 Java 프로그램에 중복 브래킷 포함 여부

import java.util.Stack;

class RedundantBrackets{ 

    static boolean checkRedundancy(String s){ 
        Stack<Character> st = new Stack<>(); 
        
        char[] str = s.toCharArray(); 
        
        for(char ch : str){ 
            if(ch == ')'){ 
                char top = st.peek(); 
                st.pop(); 
  
                boolean flag = true; 
  
                while(top != '('){ 
                    if(top == '+' || top == '-' || top == '*' || top == '/'){ 
                        flag = false; 
                    } 
    
                    top = st.peek(); 
                    st.pop(); 
                } 
                
                if(flag == true){ 
                    return true; 
                } 
            } 
            
            else{ 
                st.push(ch); 
            }                
        } 
        return false; 
    } 
  
    static void findRedundant(String str){ 
        boolean ans = checkRedundancy(str); 

        if(ans == true){ 
            System.out.println("Yes"); 
        } 
        
        else{ 
            System.out.println("No"); 
        } 
    } 
    
    public static void main(String[] args){ 
        
        String str = "((a+b))"; 
        findRedundant(str); 
  
    } 
}
Yes

복잡성 분석

시간 복잡성 : O (n) 여기서 n은 주어진 표현식의 문자 수입니다.

공간 복잡성 : O (n) n 개의 문자에 공백을 사용했기 때문입니다.

참조