+ اور - آپریٹرز پر مشتمل الجبری سٹرنگ سے بریکٹ کو ہٹا دیں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون فورکائٹس
اسٹیک سلک

مسئلہ یہ بیان

آپ کو دیا جاتا ہے 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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

اے (ن) جہاں n دیئے گئے تار میں حروف کی تعداد ہے۔ جیسا کہ ہم دیکھ سکتے ہیں کہ ہم دیئے گئے ان پٹ سٹرنگ کے عناصر کو عبور کررہے ہیں۔ اس طرح وقت کی پیچیدگی لکیری ہے۔

خلائی پیچیدگی

اے (ن) کیونکہ ہم نے حرف ذخیرہ کرنے کے لئے جگہ استعمال کی۔ چونکہ ہم نے آؤٹ پٹ کو اسٹور کرنے کے لئے ایک نئی تار تیار کی ہے تو جگہ کی پیچیدگی بھی لکیری ہوتی ہے۔