+ અને - torsપરેટર્સવાળા બીજગણિત શબ્દમાળામાંથી કૌંસને દૂર કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન ફોરકાઇટ્સ
સ્ટેક શબ્દમાળા

સમસ્યા નિવેદન

તમને આપવામાં આવે છે એ શબ્દમાળા કદ n ના કૌંસ સાથે અંકગણિત અભિવ્યક્તિનું પ્રતિનિધિત્વ કરે છે. સમસ્યા "અને + operaપરેટર્સવાળા બીજગણિત શબ્દમાળામાંથી કૌંસ કા Removeી નાખો" આપણને આપેલ અભિવ્યક્તિને સરળ બનાવવા માટે એક ફંક્શન બનાવવા માટે પૂછે છે.

ઉદાહરણ

+ અને - torsપરેટર્સવાળા બીજગણિત શબ્દમાળામાંથી કૌંસને દૂર કરો

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

+ અને - operaપરેટર્સવાળા બીજગણિત શબ્દમાળામાંથી કૌંસને દૂર કરવા માટે એલ્ગોરિધમ

  1. કૌંસ સાથે અંકગણિત અભિવ્યક્તિનું પ્રતિનિધિત્વ કરતી કદ n ના શબ્દમાળાઓ પ્રારંભ કરો.
  2. પરિણામ સંગ્રહવા માટે બીજી સ્ટ્રિંગ બનાવો. પૂર્ણાંક ચલ પ્રારંભ કરો ઇન્ડેક્સ 0 તરીકે અને પૂર્ણાંક પ્રકારનું સ્ટેક ડેટા માળખું અને તેમાં 0 દબાણ / દાખલ કરો.
  3. તે પછી, આપેલ દ્વારા પસાર કરો શબ્દમાળા તપાસો કે વર્તમાન અનુક્રમણિકામાં પાત્ર '+' ની બરાબર છે કે નહીં. અને તપાસો કે સ્ટેકની ટોચ પરનું ઘટક 1 છે કે નહીં, પરિણામ તારને અનુક્રમણિકા +1 પર '-' તરીકે અપડેટ કરો નહીંતર જો સ્ટેકની ટોચ પરનું તત્વ 0 ની બરાબર હોય, તો અનુક્રમણિકા +1 પર પરિણામ શબ્દમાળાને અપડેટ કરો. '+'.
  4. બાકી જો આપેલ શબ્દમાળામાં વર્તમાન અનુક્રમણિકાનું પાત્ર '-' ની બરાબર છે, તો સ્ટેકની ટોચ પરનું તત્વ 1 ની બરાબર છે કે નહીં તે તપાસો, પરિણામ તારને અનુક્રમણિકા +1 પર '+' તરીકે અપડેટ કરો નહીં તો જો તત્વ હોય તો સ્ટેકની ટોચ પર 0 ની બરાબર છે, પરિણામ સ્ટ્રિંગને અનુક્રમણિકા +1 પર '-' તરીકે અપડેટ કરો.
  5. એ જ રીતે, આપેલ શબ્દમાળામાં વર્તમાન અનુક્રમણિકા પરનું પાત્ર '(' અને 'ની સાથે વર્તમાન અનુક્રમણિકા 0 કરતા વધારે છે કે કેમ તે તપાસો, આપેલ શબ્દમાળામાં વર્તમાન અનુક્રમણિકા - 1 ની અક્ષર' - 'ની બરાબર છે કે કેમ તે તપાસો, પૂર્ણાંક ચલ બનાવો અને તેને 0 ની જેમ અપડેટ કરો જો સ્ટેકની ટોચ પરનું તત્વ 1 બીજું 0 ની બરાબર છે. બાકી જો વર્તમાન સૂચકાંકમાં અક્ષર - આપેલ શબ્દમાળામાં 1 '+' ની બરાબર છે, તો તત્વને દબાણ કરો. સ્ટેક પોતે સ્ટેક ટોચ.
  6. તે પછી, આપેલ શબ્દમાળામાં વર્તમાન અનુક્રમણિકા પરનું પાત્ર ')' ની બરાબર છે કે નહીં તે તપાસો, સ્ટેકની ટોચ પર તત્વ પ popપ કરો.
  7. બાકી આપેલ શબ્દમાળાના વર્તમાન અનુક્રમણિકાના પાત્ર તરીકે અનુક્રમણિકા +1 પર પરિણામ શબ્દમાળાને અપડેટ કરો.

કોડ

સી ++ પ્રોગ્રામ જેમાં + અને - torsપરેટર્સવાળા બીજગણિત શબ્દમાળામાંથી કૌંસ દૂર કરવા

#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

+ અને - operaપરેટર્સવાળા બીજગણિત શબ્દમાળામાંથી કૌંસને દૂર કરવા માટે જાવા પ્રોગ્રામ

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 આપેલ શબ્દમાળાના પાત્રોની સંખ્યા છે. જેમ આપણે જોઈ શકીએ છીએ કે આપેલ ઇનપુટ શબ્દમાળાના તત્વો ઉપર આપણે પસાર થઈ રહ્યા છીએ. આમ સમય જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (એન) કારણ કે આપણે અક્ષરો સંગ્રહિત કરવા માટે જગ્યાનો ઉપયોગ કર્યો હતો. કારણ કે આપણે આઉટપુટ સંગ્રહિત કરવા માટે એક નવું શબ્દમાળા બનાવ્યું છે, જગ્યા જટિલતા પણ રેખીય છે.