+ နှင့် - အော်ပရေတာများပါ ၀ င်သည့်အက္ခရာသင်္ချာ string မှ brackets များကိုဖယ်ရှားပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ လေးကစ်
စုပုံထား ကြိုး

ပြProbleနာဖော်ပြချက်

မင်းကို ကြိုး ကွင်းနှင့်အတူဂဏန်းသင်္ချာစကားရပ်ကိုကိုယ်စားပြုအရွယ်အစား n ၏ s ။ ပြandနာ“ + and - operator များပါ ၀ င်သည့်အက္ခရာသင်္ချာ string မှ brackets များကိုဖယ်ရှားပါ” ဟူသောပြexpressionနာကပေးထားသောစကားရပ်ကိုရိုးရှင်းစေမည့် function တစ်ခုဖန်တီးရန်တောင်းဆိုသည်။

နမူနာ

+ နှင့် - အော်ပရေတာများပါ ၀ င်သည့်အက္ခရာသင်္ချာ string မှ brackets များကိုဖယ်ရှားပါ

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

+ နှင့် - အော်ပရေတာများပါ ၀ င်သည့်အက္ခရာသင်္ချာ string မှ brackets များကိုဖယ်ရှားရန် Algorithm

  1. ကွင်းပိတ်နှင့်အတူဂဏန်းသင်္ချာစကားရပ်ကိုကိုယ်စားပြုအရွယ်အစား n ၏ string ကို s ကိုအစပြု။
  2. ရလဒ်ကိုသိမ်းဆည်းရန်အခြား string ကိုဖန်တီးပါ။ တစ်ခုကိန်း variable ကို Initialize အညွှန်းကိန်း 0 အဖြစ်နှင့်ကိန်းဂဏန်းအမျိုးအစား stack data structure နှင့်၎င်းကို ၀ င်ပါ / ထည့်သွင်းပါ။
  3. ထို့နောက်ပေးထားသောမှတဆင့်ဖြတ်သန်း string ကို။ လက်ရှိအညွှန်းကိန်းရှိစာလုံးသည် '+' နှင့်တူညီမှုရှိမရှိစစ်ဆေးပါ။ ထို့အပြင် stack ထိပ်ရှိ element သည် 1 ဟုတ်၊ မဟုတ်စစ်ဆေးပါ၊ အညွှန်း +1 ရှိရလဒ် string ကို '-' အဖြစ်ပြောင်းပါ။ သို့မဟုတ် stack ၏ထိပ်ရှိ element သည် 0 နှင့်ညီလျှင် index + 1 ရှိရလဒ် string ကို update လုပ်ပါ။ '+' ။
  4. ထို့အပြင်ပေးထားသော string ရှိလက်ရှိအညွှန်းကိန်းရှိအက္ခရာသည် '-' နှင့်ညီပါက၊ stack ထိပ်ရှိ element သည် ၁ နှင့်ညီမျှမှုရှိမရှိစစ်ဆေးပါ၊ အညွှန်း +1 ရှိရလဒ် string ကို '+' အဖြစ်အခြားအနေနှင့်မွမ်းမံပါ။ stack ရဲ့ထိပ်မှာ 1 နဲ့ညီတယ်၊ index + 0 မှာရလဒ်ကို '-' အဖြစ်ပြောင်းပါ။
  5. အလားတူစွာပင်ပေးထားသော string ရှိလက်ရှိအညွှန်းကိန်းရှိအက္ခရာသည် '(' နှင့်လက်ရှိအညွှန်းကိန်းသည် 0 ထက်ကြီးသည်၊ မမှန်လားစစ်ဆေးပါ၊ လက်ရှိအညွှန်းကိန်းရှိအက္ခရာ ၁ မှာပေးထားသော string ရှိ '-'၊ integer variable ကို create လုပ်ပြီး stack ရဲ့ထိပ်မှာရှိတဲ့ element က 1 နဲ့ 0 ဖြစ်ရင် 1 ထပ်မွမ်းမံပါ။ လက်ရှိ index မှာပါတဲ့ character က '+' နဲ့ညီရင်၊ element ကိုတွန်းပါ။ stack သူ့ဟာသူအတွက် stack ၏ထိပ်။
  6. ထိုနောက်မှပေးထားသော string ၏လက်ရှိအညွှန်းကိန်းသည် ')' နှင့်တူညီမှုရှိမရှိစစ်ဆေးပါ။
  7. အခြားအရာသည် index + 1 ရှိရလဒ် string ကိုပေးထားသော string ၏လက်ရှိအညွှန်းကိန်းအဖြစ်ဖော်ပြပါ။

ကုဒ်

+ နှင့်အော်ပရေတာများပါ ၀ င်သည့်အက္ခရာသင်္ချာ string မှ brackets များကိုဖယ်ရှားရန် C ++ Program

#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

+ and - operator များပါ ၀ င်သည့်အက္ခရာသင်္ချာ string မှ brackets များကိုဖယ်ရှားရန် Java Program

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 ကပေးထားတဲ့ string ကိုအတွက်ဇာတ်ကောင်များ၏အရေအတွက်သည်။ ကျွန်ုပ်တို့မြင်တွေ့ရသည့်အတိုင်းကျွန်ုပ်တို့သည်ပေးထားသော input string ၏ဒြပ်စင်ကိုဖြတ်ကျော်နေသည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘာဖြစ်လို့လဲဆိုတော့ငါတို့ကဇာတ်ကောင်တွေကိုသိမ်းဖို့နေရာသုံးတယ်လေ။ output ကိုသိုလှောင်ရန် string အသစ်တစ်ခုကိုကျွန်ုပ်တို့ဖန်တီးခဲ့ပြီးသောကြောင့် space ရှုပ်ထွေးမှုသည်လည်း linear ဖြစ်သည်။