+ 및 – 연산자를 포함하는 대수 문자열에서 대괄호 제거

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 포카이트
스택 조회수 84

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

문제 정책

당신은 주어진 괄호가있는 산술 식을 나타내는 n 크기의 s. "+ 및 – 연산자를 포함하는 대수 문자열에서 대괄호 제거"문제는 주어진 표현식을 단순화 할 수있는 함수를 만들도록 요청합니다.

+ 및 – 연산자를 포함하는 대수 문자열에서 대괄호 제거

s = "a-(b+c)"
a-b-c
 s = a-(b-c-(d+e))-f
a-b+c+d+e-f

+ 및 – 연산자를 포함하는 대수 문자열에서 대괄호를 제거하는 알고리즘

  1. 괄호가있는 산술 표현식을 나타내는 n 크기의 문자열 s를 초기화합니다.
  2. 결과를 저장할 다른 문자열을 만듭니다. 정수 변수 초기화 색인 0 및 정수 유형의 스택 데이터 구조로 0을 푸시 / 삽입합니다.
  3. 그 후, 주어진 끈. 현재 색인의 문자가 '+'와 같은지 확인하십시오. 그리고 스택 맨 위에있는 요소가 1인지 확인하고 인덱스 + 1의 결과 문자열을 '-'로 업데이트하고 스택 맨 위에있는 요소가 0이면 결과 문자열을 인덱스 + 1로 업데이트합니다. '+'.
  4. 그렇지 않으면 주어진 문자열의 현재 인덱스에있는 문자가 '-'와 같으면 스택의 맨 위에있는 요소가 1인지 확인하고 인덱스 + 1의 결과 문자열을 '+'로 업데이트합니다. 스택의 맨 위가 0이면 인덱스 + 1의 결과 문자열을 '-'로 업데이트합니다.
  5. 마찬가지로 주어진 문자열의 현재 인덱스에있는 문자가 '('와 같고 현재 인덱스가 0보다 큰지 확인하고, 현재 인덱스의 문자가 주어진 문자열에서 1 인 경우 '-'와 같은지 확인합니다. 정수 변수를 생성하고 스택 맨 위에있는 요소가 0과 같으면 1으로 업데이트합니다. 그렇지 않으면 현재 인덱스의 문자 – 주어진 문자열에서 0이 '+'와 같으면 요소를 스택 자체의 맨 위.
  6. 그 후 주어진 문자열의 현재 색인에있는 문자가 ')'와 같은지 확인하고 스택 맨 위에있는 요소를 팝합니다.
  7. 그렇지 않으면 주어진 문자열의 현재 인덱스에있는 문자로 인덱스 + 1의 결과 문자열을 업데이트합니다.

암호

+ 및 – 연산자를 포함하는 대수 문자열에서 대괄호를 제거하는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
char* simplify(string s){ 
    int n = s.length(); 
  
    char* res = new char(n); 
    int index = 0, i = 0; 
  
    stack<int> st; 
    st.push(0); 
  
    while(i < n){ 
        if(s[i] == '+'){ 
            
            if(st.top() == 1){ 
                res[index++] = '-';
            }
            
            if(st.top() == 0){ 
                res[index++] = '+'; 
            }
        } 
        
        else if(s[i] == '-'){ 
            
            if(st.top() == 1){ 
                res[index++] = '+';
            }
            
            else if(st.top() == 0){ 
                res[index++] = '-';
            }
        } 
        
        else if(s[i] == '(' && i > 0){ 
            
            if(s[i - 1] == '-'){ 
                int x = (st.top() == 1) ? 0 : 1; 
                st.push(x); 
            } 
  
            else if(s[i - 1] == '+'){ 
                st.push(st.top()); 
            }
        } 
  
        else if(s[i] == ')'){ 
            st.pop(); 
        }
  
        else{
            res[index++] = s[i];
        }
        i++; 
    } 
    return res; 
} 
  
int main(){ 
    string s = "a-(b+c)"; 
    cout << simplify(s) << endl; 
    return 0; 
}
a-b-c

+ 및 – 연산자를 포함하는 대수 문자열에서 대괄호를 제거하는 Java 프로그램

import java.util.*; 

class SimplifyExp{  
  
    static String simplify(String s){  
        int n = s.length();  
      
        char res[] = new char[n];  
        int index = 0, i = 0;  
      
        Stack<Integer> st = new Stack<Integer> ();  
        st.push(0);  
      
        while(i < n){  
            if(s.charAt(i) == '+'){  
      
                if(st.peek() == 1){  
                    res[index++] = '-';
                }
      
                if(st.peek() == 0){  
                    res[index++] = '+';
                }
            } 
            
            else if(s.charAt(i) == '-'){  
                
                if(st.peek() == 1){  
                    res[index++] = '+';
                }
                
                else if(st.peek() == 0){  
                    res[index++] = '-'; 
                }
            } 
            
            else if(s.charAt(i) == '(' && i > 0){
                
                if(s.charAt(i - 1) == '-'){  
                    int x = (st.peek() == 1) ? 0 : 1;  
                    st.push(x);  
                }  
      
                else if(s.charAt(i - 1) == '+'){  
                    st.push(st.peek());  
                }
            }  
      
            else if(s.charAt(i) == ')'){  
                st.pop();  
            }
      
            else{
                res[index++] = s.charAt(i);
            }
            i++;  
        }  
        return new String(res);  
    }  
      
    public static void main(String[] args){  
        String s = "a-(b+c)";  
        System.out.println(simplify(s));  
    } 
}
a-b-c

복잡성 분석

시간 복잡성

O (N) 여기서 n은 주어진 문자열의 문자 수입니다. 우리가 주어진 입력 문자열의 요소를 순회하고 있음을 알 수 있습니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

O (N) 문자를 저장하기 위해 공간을 사용했기 때문입니다. 출력을 저장하기 위해 새 문자열을 만들었으므로 공간 복잡성도 선형입니다.

균열 시스템 설계 인터뷰
Translate »