+および–演算子を含む代数文字列から角かっこを削除します


難易度 ミディアム
よく聞かれる Adobe Amazon (アマゾン) フォーカイテス
スタック 文字列

問題文

あなたは与えられます 文字列 サイズ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. 結果を保存する別の文字列を作成します。 整数変数を初期化します index 0および整数型のスタックデータ構造として、0をプッシュ/挿入します。
  3. その後、与えられたものをトラバースします 文字列。 現在のインデックスの文字が「+」に等しいかどうかを確認します。 そして、スタックの一番上の要素が1であるかどうかを確認し、インデックス+1の結果文字列を「-」として更新します。そうでない場合、スタックの一番上の要素が0に等しい場合は、インデックス+1の結果文字列を次のように更新します。 '+'。
  4. それ以外の場合、指定された文字列の現在のインデックスの文字が「-」に等しい場合は、スタックの最上位の要素が1に等しいかどうかを確認し、インデックス+1の結果文字列を「+」として更新します。スタックの最上位が0に等しい場合、インデックス+1の結果文字列を「-」として更新します。
  5. 同様に、指定された文字列の現在のインデックスの文字が '('に等しく、現在のインデックスが0より大きいかどうかを確認し、指定された文字列の現在のインデックス–1の文字が '-'に等しいかどうかを確認します。整数変数を作成し、スタックの最上位の要素が0に等しい場合は1に更新し、それ以外の場合は0に更新します。それ以外の場合、現在のインデックスの文字–指定された文字列の1が '+'に等しい場合は、要素をスタック自体のスタックの最上位。
  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) 文字を格納するためにスペースを使用したためです。 出力を格納するための新しい文字列を作成したため、スペースの複雑さも線形です。