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

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

문제 정책

당신은 주어진 괄호가있는 산술 식을 나타내는 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 »