차례
문제 정책
당신은 주어진 현 괄호가있는 산술 식을 나타내는 n 크기의 s. "+ 및 – 연산자를 포함하는 대수 문자열에서 대괄호 제거"문제는 주어진 표현식을 단순화 할 수있는 함수를 만들도록 요청합니다.
예
s = "a-(b+c)"
a-b-c
s = a-(b-c-(d+e))-f
a-b+c+d+e-f
+ 및 – 연산자를 포함하는 대수 문자열에서 대괄호를 제거하는 알고리즘
- 괄호가있는 산술 표현식을 나타내는 n 크기의 문자열 s를 초기화합니다.
- 결과를 저장할 다른 문자열을 만듭니다. 정수 변수 초기화 색인 0 및 정수 유형의 스택 데이터 구조로 0을 푸시 / 삽입합니다.
- 그 후, 주어진 끈. 현재 색인의 문자가 '+'와 같은지 확인하십시오. 그리고 스택 맨 위에있는 요소가 1인지 확인하고 인덱스 + 1의 결과 문자열을 '-'로 업데이트하고 스택 맨 위에있는 요소가 0이면 결과 문자열을 인덱스 + 1로 업데이트합니다. '+'.
- 그렇지 않으면 주어진 문자열의 현재 인덱스에있는 문자가 '-'와 같으면 스택의 맨 위에있는 요소가 1인지 확인하고 인덱스 + 1의 결과 문자열을 '+'로 업데이트합니다. 스택의 맨 위가 0이면 인덱스 + 1의 결과 문자열을 '-'로 업데이트합니다.
- 마찬가지로 주어진 문자열의 현재 인덱스에있는 문자가 '('와 같고 현재 인덱스가 0보다 큰지 확인하고, 현재 인덱스의 문자가 주어진 문자열에서 1 인 경우 '-'와 같은지 확인합니다. 정수 변수를 생성하고 스택 맨 위에있는 요소가 0과 같으면 1으로 업데이트합니다. 그렇지 않으면 현재 인덱스의 문자 – 주어진 문자열에서 0이 '+'와 같으면 요소를 스택 자체의 맨 위.
- 그 후 주어진 문자열의 현재 색인에있는 문자가 ')'와 같은지 확인하고 스택 맨 위에있는 요소를 팝합니다.
- 그렇지 않으면 주어진 문자열의 현재 인덱스에있는 문자로 인덱스 + 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) 문자를 저장하기 위해 공간을 사용했기 때문입니다. 출력을 저장하기 위해 새 문자열을 만들었으므로 공간 복잡성도 선형입니다.
