식에서 일치하지 않는 괄호 식별 및 표시

난이도 중급
자주 묻는 질문 TCS
스택 끈조회수 46
링크드 인버퍼레딧텀블러

표현 문제에서 일치하지 않는 괄호를 식별하고 표시 할 때 현 표현식을 포함하는 길이 n의 s. 균형 잡힌 괄호 쌍을 찾아 모든 균형 여는 괄호를 0으로, 균형 잡힌 닫는 괄호를 1로, 불균형 괄호를 -1로 바꿉니다.

예

주어진 문자열 s =“(((abc)) ((d)))))”를 보자. 여기서 주어진 문자열을 사용하는 표현식에서 일치하지 않는 괄호를 식별하고 표시합니다.

여기서 첫 번째 괄호는 마지막 세 번째 괄호와 균형을 이룹니다. 따라서 여는 괄호와 닫는 괄호를 각각 0과 1로 바꿉니다.

  • 그 후 두 번째 괄호는 하위 표현식 "abc"의 두 번째 닫는 괄호와 균형을 이루므로 여는 괄호와 닫는 괄호를 각각 0과 1로 바꿉니다.
  • 마찬가지로 세 번째 괄호는 하위 표현식 "abc"의 첫 번째 닫는 괄호와 균형을 이루므로 여는 괄호와 닫는 괄호를 각각 0과 1로 바꿉니다.
  • 네 번째 여는 괄호는 하위 표현식 "d"의 두 번째 닫는 괄호와 균형을 이루므로 여는 괄호와 닫는 괄호를 각각 0과 1로 바꿉니다.
  • 마찬가지로 다섯 번째 여는 괄호는 하위 표현식 "d"의 첫 번째 닫는 괄호와 균형을 이루므로 여는 괄호와 닫는 괄호를 각각 0과 1로 바꿉니다.
  • 마지막으로 모든 불균형 괄호를 -1로 바꿉니다.
  • 따라서 결과 = 000abc1100d111-1-1

식에서 일치하지 않는 괄호 식별 및 표시핀

입력 : s =“((a)”

출력 : -10a1

입력 : s =“(a))”

출력 : 0a1-1

식에서 일치하지 않는 괄호를 식별하고 표시하는 알고리즘

  1. 표현식을 포함하는 길이 n의 문자열 s를 초기화합니다.
  2. 만들기 스택 데이터 구조.
  3. 주어진 문자열을 탐색하고 문자열의 현재 인덱스에있는 문자가 여는 괄호와 같은지 확인하고 스택에 현재 인덱스를 푸시 / 삽입합니다.
  4. 그렇지 않으면 문자열의 현재 인덱스에있는 문자가 닫는 괄호와 같은지 확인하고, 스택이 비어 있는지 확인하고, 문자열의 현재 인덱스에있는 문자를 -1로 바꾸거나 업데이트합니다. 그렇지 않으면 모든 여는 괄호를 0으로, 닫는 괄호를 1로 바꿉니다.
  5. 스택이 비어 있지 않은 동안 스택의 모든 문자를 -1로 업데이트합니다.
  6. 업데이트 된 문자열을 인쇄합니다.

식에서 일치하지 않는 괄호를 식별하고 표시하는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
void identifyParenthesis(string s){
    stack<int> st; 
  
    for(int i = 0; i < s.length(); i++){ 
        if(s[i] == '('){  
            st.push(i); 
        }
          
        else if(s[i] == ')'){ 
  
            if(st.empty()){  
                s.replace(i, 1, "-1"); 
            }
              
            else{ 
                s.replace(i, 1, "1"); 
                s.replace(st.top(), 1, "0"); 
                st.pop(); 
            } 
        } 
    } 
  
    while(!st.empty()){ 
        s.replace(st.top(), 1, "-1"); 
        st.pop(); 
    } 
  
    cout << s << endl; 
} 
  
int main(){ 
    string s = "(a))"; 
    
    identifyParenthesis(s); 
    
    return 0; 
}
0a1-1

표현식에서 일치하지 않는 괄호를 식별하고 표시하는 Java 프로그램

import java.util.*; 
  
class MarkParenthesis{ 
    
    static void identifyParenthesis(StringBuffer s){  
        Stack<Integer> st = new Stack<Integer>();  
      
        for(int i = 0; i < s.length(); i++){  
            if (s.charAt(i) == '('){  
                st.push(i);  
            }
              
            else if(s.charAt(i) == ')'){  
                if(st.empty()){  
                    s.replace(i, i + 1, "-1");  
                }
                  
                else{  
                    s.replace(i, i + 1, "1");  
                    s.replace(st.peek(), st.peek() + 1, "0");  
                    st.pop();  
                }  
            }  
        }  
      
        while(!st.empty()){  
            s.replace(st.peek(), 1, "-1");  
            st.pop();  
        }  
      
        System.out.println(s); 
    }  
      
    public static void main(String[] args){
        
        StringBuffer s = new StringBuffer("(a))");  
        identifyParenthesis(s);  
        
    } 
}
0a1-1

복잡성 분석

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

공간 복잡성 : n 개의 요소를 저장하기 위해 공간을 사용했기 때문에 O (n).

참조

링크드 인버퍼레딧텀블러
Translate »