+ සහ - ක්‍රියාකරුවන් අඩංගු වීජීය නූලකින් වරහන් ඉවත් කරන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් ෆෝකයිට්
අඩුක්කුව String

ගැටළු ප්රකාශය

ඔබට ලබා දී ඇත්තේ අ පේළියකි ප්‍රමාණයේ n වරහන් සමඟ ගණිත ප්‍රකාශනයක් නිරූපණය කරයි. “+ සහ - ක්‍රියාකරුවන් අඩංගු වීජීය නූලකින් වරහන් ඉවත් කරන්න” යන ගැටළුව අපෙන් ඉල්ලා සිටින්නේ දී ඇති ප්‍රකාශනය සරල කළ හැකි ශ්‍රිතයක් නිර්මාණය කරන ලෙසයි.

උදාහරණයක්

+ සහ - ක්‍රියාකරුවන් අඩංගු වීජීය නූලකින් වරහන් ඉවත් කරන්න

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

+ සහ - ක්‍රියාකරුවන් අඩංගු වීජීය නූලකින් වරහන් ඉවත් කිරීමට ඇල්ගොරිතම

  1. වරහන් සමඟ අංක ගණිත ප්‍රකාශනයක් නිරූපණය කරන n ප්‍රමාණයේ නූලක් ආරම්භ කරන්න.
  2. ප්‍රති .ලය ගබඩා කිරීම සඳහා තවත් නූලක් සාදන්න. පූර්ණ සංඛ්‍යා විචල්‍යයක් ආරම්භ කරන්න දර්ශකය 0 ලෙස සහ පූර්ණ සංඛ්‍යා වර්ගයේ දත්ත ව්‍යුහයක් සහ එය තුළට 0 / ඇතුළු කරන්න.
  3. ඊට පසු, දී ඇති දේ හරහා ගමන් කරන්න නූල්. වත්මන් දර්ශකයේ අක්‍ෂරය '+' ට සමාන දැයි පරීක්ෂා කරන්න. තොගයේ මුදුනේ ඇති මූලද්‍රව්‍යය 1 දැයි පරීක්ෂා කර බලන්න, ප්‍රති + ල + 1 දර්ශකයේ '-' ලෙස යාවත්කාලීන කරන්න. '+'.
  4. ලබා දී ඇති නූලෙහි වත්මන් දර්ශකයේ අක්‍ෂරය '-' ට සමාන නම්, තොගයේ ඉහළින් ඇති මූලද්‍රව්‍යය 1 ට සමාන දැයි පරීක්ෂා කරන්න, ප්‍රති result ල + 1 දර්ශකයේ '+' ලෙස යාවත්කාලීන කරන්න. තොගයේ ඉහළින් 0 ට සමාන වේ, ප්‍රති result ල දණ්ඩ + 1 දර්ශකයේ '-' ලෙස යාවත්කාලීන කරන්න.
  5. ඒ හා සමානව, දී ඇති නූලෙහි වත්මන් දර්ශකයේ අක්‍ෂරය '(' ට සමානද යන්න සහ වත්මන් දර්ශකය 0 ට වඩා වැඩි නම්, ලබා දී ඇති නූල් - 1 හි ඇති අක්‍ෂරය '-' ට සමාන දැයි පරීක්ෂා කරන්න, පූර්ණ සංඛ්‍යා විචල්‍යයක් සාදා එය 0 ලෙස යාවත්කාලීන කරන්න. තොගයේ ඉහළින් ඇති මූලද්‍රව්‍යය වෙනත් 1 ට සමාන වේ. තොගයේ මුදුනේම.
  6. ඊට පසු, දී ඇති නූලෙහි වත්මන් දර්ශකයේ අක්‍ෂරය ')' ට සමාන දැයි පරීක්ෂා කරන්න, මූලද්රව්යයේ මුදුනේ ඇති අංගය පොප් කරන්න.
  7. ලබා දී ඇති නූලෙහි වත්මන් දර්ශකයේ අක්‍ෂරය ලෙස + 1 දර්ශකයේ ප්‍රති result ල දණ්ඩ යාවත්කාලීන කරන්න.

කේතය

+ සහ - ක්‍රියාකරුවන් අඩංගු වීජීය නූලකින් වරහන් ඉවත් කිරීමේ 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

+ සහ - ක්‍රියාකරුවන් අඩංගු වීජීය නූලකින් වරහන් ඉවත් කිරීමට ජාවා වැඩසටහන

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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

සාමාන්ය (n) මෙහි n යනු දී ඇති නූලෙහි ඇති අක්ෂර ගණන වේ. ලබා දී ඇති ආදාන නූලෙහි මූලද්‍රව්‍යයන් හරහා අප ගමන් කරන බව අපට පෙනෙන පරිදි. මේ අනුව කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) අපි අක්ෂර ගබඩා කිරීමට අවකාශය භාවිතා කළ නිසා. ප්‍රතිදානය ගබඩා කිරීම සඳහා අප නව නූලක් නිර්මාණය කර ඇති බැවින් අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.