대체와 균형 잡힌 표현

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

Balanced Expression with Replacement 문제에서는 '(', ')', '[', ']', '{', '}'와 같은 괄호를 포함하는 문자열 s를 제공했습니다. 그만큼 또한 괄호 대신 x를 포함합니다. 모든 x를 괄호로 바꾼 후 문자열을 유효한 괄호가있는 표현식으로 변환 할 수 있는지 확인하십시오.

대체와 균형 잡힌 표현

입력 

s =“{(x [x])}”

산출

 가능

입력

s =“[{x} (x)]”

산출 

아니

암호알고리즘

이제 우리는 균형 잡힌 표현과 교체 문제의 문제 진술을 알고 있습니다. 그래서 우리는 솔루션에 대한 아래 알고리즘에 왔습니다.

  1. 문자열 s, 문자 유형 스택 및 변수를 초기화하여 현재 인덱스를 0으로 저장합니다.
  2. 문자열의 길이가 현재 인덱스와 같으면 스택이 비어 있으면 1을 반환하고 0을 반환합니다.
  3. 문자열의 현재 인덱스에있는 문자가 여는 괄호인지 확인하고 스택에 푸시 한 다음 현재 인덱스를 현재 인덱스 +1로 사용하여 재귀 호출을 반환합니다.
  4. 그렇지 않으면 문자열의 현재 인덱스에있는 문자가 닫는 괄호이면 스택이 비어 있는지 확인하고 0을 반환합니다. 그렇지 않으면 스택의 맨 위가 문자열의 현재 문자에 ​​대한 여는 괄호와 같지 않은지 확인하고 0을 반환합니다. top 및 현재 인덱스를 현재 인덱스 +1로 사용하여 재귀 호출을 반환합니다.
  5. 그렇지 않으면 문자열의 현재 인덱스에있는 문자가 x와 같으면 이전 스택과 동일한 임시 스택을 만들고 그 문자를 밀어 넣습니다.
  6. 변수 res를 만듭니다. 현재 인덱스를 현재 인덱스 +1 및 임시 스택으로 사용하여 재귀 호출을 수행합니다. 결과를 res에 저장하십시오.
  7. res가 1이면 1을 반환합니다.
  8. 이전 스택이 비어 있으면 0을 반환합니다.
  9. 이전 스택에서 맨 위를 팝하고 현재 인덱스가 현재 인덱스 +1 및 이전 스택 인 재귀 호출을 반환합니다.

대체가있는 균형 잡힌 표현을위한 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
int isMatching(char a, char b){ 
    if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x') 
      return 1; 
    return 0; 
} 
  
int isBalanced(string s, stack<char> ele, int ind){ 
  
    if(ind == s.length()){  
        return ele.empty();
    }
  
    char topEle; 
  
    int res; 
  
    if((s[ind] == '{') || (s[ind] == '(') || (s[ind] == '[')){ 
        ele.push(s[ind]); 
        return isBalanced(s, ele, ind + 1); 
    } 
  
    else if((s[ind] == '}') || (s[ind] == ')') || (s[ind] == ']')){ 
  
        if(ele.empty()){  
            return 0; 
        }
  
        topEle = ele.top(); 
        ele.pop(); 
  
        if(!isMatching(topEle, s[ind])){  
            return 0; 
        }
          
        return isBalanced(s, ele, ind + 1); 
    } 
  
    else if(s[ind] == 'x'){ 
        stack<char> tmp = ele; 
        tmp.push(s[ind]); 
        res = isBalanced(s, tmp, ind + 1); 
        if(res){ 
            return 1;
        }
        if(ele.empty()){ 
            return 0; 
        }
        ele.pop();
        
        return isBalanced(s, ele, ind + 1); 
    } 
} 
  
int main(){ 
    string s = "{(x[x])}"; 
    stack<char> ele;
    
    if(isBalanced(s, ele, 0)){  
        cout<<"Yes";   
    }
    
    else{ 
        cout<<"No";
    }
    return 0; 
}
Yes

균형 잡힌 표현을위한 자바 프로그램 (대체 포함)

import java.util.Stack; 
  
class BalancedExpression{ 
    
    static int isMatching(char a, char b){ 
        if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x'){ 
            return 1; 
        } 
        return 0; 
    } 
  
    static int isBalanced(String s, Stack<Character> ele, int ind){ 
  
        if(ind == s.length()){ 
            if(ele.size() == 0){ 
                return 1; 
            } 
            else{ 
                return 0; 
            } 
        } 
  
        char topEle; 
  
        int res; 
  
        if((s.charAt(ind) == '{') || (s.charAt(ind) == '(') || (s.charAt(ind) == '[')){ 
            ele.push(s.charAt(ind)); 
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if((s.charAt(ind) == '}') || (s.charAt(ind) == ')') || (s.charAt(ind) == ']')){ 
  
            if(ele.size() == 0){ 
                return 0; 
            } 
  
            topEle = ele.peek(); 
            ele.pop(); 
  
            if(isMatching(topEle, s.charAt(ind)) == 0){ 
                return 0; 
            } 
  
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if(s.charAt(ind) == 'x'){ 
            Stack<Character> tmp = new Stack<>(); 
            
            tmp.addAll(ele);  
            tmp.push(s.charAt(ind)); 
            res = isBalanced(s, tmp, ind + 1); 
            
            if(res == 1){ 
                return 1; 
            } 
            
            if(ele.size() == 0){ 
                return 0; 
            } 
            
            ele.pop(); 
            return isBalanced(s, ele, ind + 1); 
        } 
        return 1; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "{(x[x])}"; 
        Stack<Character> ele = new Stack<Character>(); 
  
        if(isBalanced(s, ele, 0) != 0){ 
            System.out.println("Yes"); 
        } 
        
        else{ 
            System.out.println("No"); 
        } 
    } 
}
Yes

복잡성 분석

시간 복잡성 : O ((2 ^ n) * n) 여기서 n은 문자열의 길이입니다.

보조 공간 : O (n) 스택에 n 개의 추가 공간을 사용했기 때문입니다.

참조

Translate »