식에 중복 괄호가 있는지 여부 찾기

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

주어진 현 균형 잡힌 괄호를 포함합니다. 표현식 / 문자열에 중복 괄호가 포함되어 있는지 확인합니다.

중복 괄호

표현식이 동일한 유형의 균형 잡힌 괄호의 중간에 있거나 둘러싸여있는 경우, 즉 동일한 유형의 여는 괄호와 닫는 괄호 사이에 두 번 이상 포함 된 경우 중복 괄호가 있다고합니다. 예를 들어 – ((a + b)) 즉 전체 표현식이 두 개의 유사한 괄호 중간에 있지만 표현식 (a + (b))에서는 전체 표현식이나 하위 표현식에 중복 괄호가 없습니다.

예를 들어 –

핀

예

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

출력: 표현식에 중복 된 괄호가 있습니다.

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

출력: 표현식에 중복 된 괄호가 없습니다.

스택 사용 방법

스택을 만듭니다. 주어진 문자열을 순회하거나 반복합니다. 각 문자가 '('또는 연산자 또는 피연산자와 같으면 스택으로 푸시합니다. 그렇지 않으면 ')'와 같으면 동일한 종류의 여는 괄호를 찾을 때까지 문자를 팝합니다. 개수 변수가 사용되며 여는 괄호 '('가 발견 될 때까지 모든 문자에 대해 증분합니다. 변수 개수가 1보다 작 으면 true를 반환하고 그렇지 않으면 중복 괄호가 발견되지 않습니다.

암호알고리즘

1. 균형 잡힌 괄호가 포함 된 문자열 식을 초기화합니다.
2. 초기화 스택 문자를 저장합니다.
3. 문자열을 탐색하고 현재 문자가 닫는 괄호가 아닌지 확인하고 해당 문자를 스택으로 밀어 넣습니다.
4. 그렇지 않으면 스택의 상단을 팝하고 카운터를 초기화하여 괄호 안의 요소를 0으로 계산합니다. 상단이 여는 괄호와 같지 않은 동안 카운터를 증가시키고 상단을 팝합니다.
5. 내부 요소가 1보다 작은 지 확인하고 1을 반환합니다.
6. 거짓을 반환합니다.

Expression 용 C ++ 프로그램에 중복 괄호가 있거나 없습니다.

#include <bits/stdc++.h> 
using namespace std; 
  
bool isDuplicate(string s){ 
    
    stack<char> Stack; 
  
    for(char ch : s){ 
        
        if(ch == ')'){ 
            
            char top = Stack.top(); 
            Stack.pop(); 
  
            int elementsInside = 0; 
            
            while(top != '('){ 
                elementsInside++; 
                top = Stack.top(); 
                Stack.pop(); 
            } 
            
            if(elementsInside < 1){ 
                return 1; 
            } 
        } 
  
        else{
            Stack.push(ch); 
        }    
    } 
  
    return false; 
} 
  
  
int main(){ 
    
    string s = "(((a+(b))+(c+d)))"; 
  
    if(isDuplicate(s)){ 
        cout<<"Expression contains duplicate parenthesis.";
    }    
    else{
        cout<<"Expression does not contain duplicate parenthesis."; 
    }    
  
    return 0; 
}

Expression contains duplicate parenthesis.

Expression 용 Java 프로그램에 중복 된 괄호가 있거나 없습니다.

import java.util.Stack; 
  
class Parenthesis{ 
  
    static boolean isDuplicate(String s){ 
        
        Stack<Character> Stack = new Stack<>(); 
  
        char[] str = s.toCharArray(); 
        for(char ch : str) { 
            
            if (ch == ')') { 
                
                char top = Stack.peek(); 
                Stack.pop(); 
  
                int elementsInside = 0; 
                
                while (top != '(') { 
                    elementsInside++; 
                    top = Stack.peek(); 
                    Stack.pop(); 
                } 
                
                if (elementsInside < 1){ 
                    return true; 
                } 
            } 
            
            else{ 
                Stack.push(ch); 
            } 
        } 
  
        return false; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "(((a+(b))+(c+d)))"; 
  
        if(isDuplicate(s)){ 
            System.out.println("Expression contains duplicate parenthesis."); 
        } 
        
        else{ 
            System.out.println("Expression does not contain duplicate parenthesis."); 
        } 
  
    } 
}

Expression contains duplicate parenthesis.

식에 대한 복잡성 분석에 중복 괄호가 있거나 없습니다.

시간 복잡성 : O (n) 여기서 n은 expression의 문자 수입니다.

보조 공간 : O (n) 문자를 저장하기 위해 스택 공간을 사용했기 때문입니다.

참조