+ आणि - ऑपरेटर असलेल्या बीजगणित स्ट्रिंगमधून कंस काढा


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन फोरकाइट्स
स्टॅक अक्षरमाळा

समस्या विधान

आपल्याला दिले जाते a स्ट्रिंग कंसांसह अंकगणितात्मक अभिव्यक्तीचे प्रतिनिधित्व करणारे आकार 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 वर 'स्ट्रिंग' म्हणून '-' म्हणून अद्यतनित करा अन्यथा स्टॅकच्या शीर्षस्थानी घटक 0 बरोबर असल्यास, अनुक्रमणिका + 1 वर परिणाम स्ट्रिंग अद्यतनित करा. '+'.
  4. अन्यथा दिलेल्या निर्देशांकातील सध्याच्या निर्देशांकामधील वर्ण '-' च्या बरोबरीचे असल्यास, स्टॅकच्या शीर्षस्थानी घटक 1 बरोबर आहे की नाही ते तपासा, अनुक्रमणिका + 1 वर परिणाम स्ट्रिंग '+' म्हणून अद्यतनित करा अन्यथा घटक असल्यास स्टॅकच्या शीर्षस्थानी 0 च्या बरोबरीने, अनुक्रमणिका + 1 वर 'स्ट्रिंग' म्हणून 'स्ट्रिंग' अपडेट करा.
  5. त्याचप्रमाणे, दिलेल्या स्ट्रिंगमधील सध्याच्या निर्देशांकामधील वर्ण '(') बरोबर आहे आणि वर्तमान निर्देशांक 0 पेक्षा मोठे आहे का ते तपासा, दिलेल्या निर्देशांकातील वर्तमान निर्देशांक - 1 मधील वर्ण '-' बरोबर आहे का ते तपासा. पूर्णांक व्हेरिएबल तयार करा आणि स्टॅकच्या शीर्षावरील घटक 0 इतर 1 च्या समान असल्यास 0 असे अद्यतनित करा. अन्यथा वर्तमान निर्देशांकातील वर्ण - 1 दिलेल्या स्ट्रिंगमधील वर्ण '+' बरोबर असल्यास, त्या घटकाला दाबा. स्टॅकमध्येच स्टॅकच्या वरच्या बाजूस.
  6. त्यानंतर, दिलेल्या स्ट्रिंगमधील वर्तमान निर्देशांकामधील वर्ण ')' बरोबर आहे का ते तपासा, स्टॅकच्या शीर्षस्थानी घटक पॉप करा.
  7. अन्यथा दिलेल्या स्ट्रिंगमधील वर्तमान निर्देशांकावरील वर्ण म्हणून अनुक्रमणिका + 1 वर परिणाम स्ट्रिंग अद्यतनित करा.

कोड

+ आणि - ऑपरेटर असलेल्या बीजगणित स्ट्रिंगमधून कंस काढण्यासाठी सी ++ प्रोग्राम

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे एन दिलेली स्ट्रिंगमधील वर्णांची संख्या आहे. जसे आपण पाहू शकतो की दिलेल्या इनपुट स्ट्रिंगच्या घटकांवर आपण मागे फिरत आहोत. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

O (n) कारण आम्ही अक्षरे संचयित करण्यासाठी जागा वापरली. आऊटपुट साठवण्यासाठी नवीन स्ट्रिंग तयार केल्यामुळे स्पेस कॉम्प्लेक्सिटीसुद्धा रेषात्मक आहे.