ຖອດວົງເລັບອອກຈາກສາຍອັກຂະຄະນິດສາດທີ່ປະກອບດ້ວຍ + ແລະ - ປະຕິບັດການ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ສີ່ພັນ
Stack string

ຖະແຫຼງການບັນຫາ

ເຈົ້າຍັງບໍ່ໄດ້ໃຫ້ string s of size n ທີ່ເປັນຕົວແທນຂອງການສະແດງອອກເລກຄະນິດສາດກັບວົງເລັບ. ບັນຫາ“ ເອົາວົງເລັບອອກຈາກສາຍອັກຂະຄະນິດທີ່ບັນຈຸ + ແລະ - ຜູ້ປະຕິບັດງານ” ຂໍໃຫ້ພວກເຮົາສ້າງ ໜ້າ ທີ່ທີ່ສາມາດສະແດງອອກໃຫ້ງ່າຍຂື້ນ.

ຍົກຕົວຢ່າງ

ຖອດວົງເລັບອອກຈາກສາຍອັກຂະຄະນິດສາດທີ່ປະກອບດ້ວຍ + ແລະ - ປະຕິບັດການ

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

ສູດການຄິດໄລ່ທີ່ຈະເອົາວົງເລັບອອກຈາກສາຍອັກຂະຄະນິດສາດທີ່ປະກອບດ້ວຍ + ແລະ - ຜູ້ປະຕິບັດງານ

  1. ເລີ່ມຕົ້ນສາຍ s ຂະ ໜາດ n ສະແດງອອກດ້ວຍການຄິດໄລ່ເລກເລກກັບວົງເລັບ.
  2. ສ້າງສາຍອື່ນເພື່ອເກັບຜົນໄດ້ຮັບ. ເລີ່ມຕົ້ນຕົວແປຍ່ອຍ ດັດຊະນີ ເປັນ 0 ແລະໂຄງສ້າງຂໍ້ມູນ stack ຂອງປະເພດເລກເຕັມແລະຍູ້ / ໃສ່ 0 ໃນນັ້ນ.
  3. ຫລັງຈາກນັ້ນ, ຂ້າມຜ່ານໄປ string ກວດເບິ່ງວ່າຕົວລະຄອນໃນດັດຊະນີປັດຈຸບັນເທົ່າກັບ '+'. ແລະກວດເບິ່ງວ່າອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ແມ່ນ 1, ປັບປຸງຊ່ອຍແນ່ຜົນໄດ້ຮັບທີ່ດັດຊະນີ + 1 ເປັນ '-' ອື່ນຖ້າວ່າອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ແມ່ນເທົ່າກັບ 0, ປັບປຸງສະຕິງຜົນທີ່ດັດຊະນີ + 1 ຄື '+'.
  4. ອື່ນຖ້າຕົວລະຄອນທີ່ດັດສະນີປັດຈຸບັນໃນສະຕິງທີ່ໃຫ້ນັ້ນເທົ່າກັບ '-', ກວດເບິ່ງວ່າອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ແມ່ນເທົ່າກັບ 1, ປັບປຸງສະຕິງຜົນທີ່ດັດຊະນີ + 1 ເປັນ '+' ອີກຖ້າວ່າອົງປະກອບ ຢູ່ເທິງສຸດຂອງ stack ແມ່ນເທົ່າກັບ 0, ປັບປຸງສະຕິງຜົນໄດ້ຮັບທີ່ດັດຊະນີ + 1 ເປັນ '-'.
  5. ເຊັ່ນດຽວກັນ, ກວດເບິ່ງວ່າຕົວລະຄອນທີ່ດັດສະນີປັດຈຸບັນໃນສະຕິງທີ່ມອບໃຫ້ເທົ່າກັບ '(' ແລະດັດຊະນີປັດຈຸບັນແມ່ນໃຫຍ່ກວ່າ 0, ກວດເບິ່ງວ່າຕົວລະຄອນທີ່ດັດສະນີປັດຈຸບັນ - 1 ໃນສະຕິງທີ່ມອບໃຫ້ເທົ່າກັບ '-', ສ້າງຕົວແປເຕັມແລະປັບປຸງໃຫ້ມັນເປັນ 0 ຖ້າວ່າອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ແມ່ນເທົ່າກັບ 1 ອີກ 0. ອື່ນຖ້າວ່າຕົວລະຄອນໃນດັດຊະນີປັດຈຸບັນ - 1 ໃນສະຕິງທີ່ໃຫ້ໄວ້ເທົ່າກັບ '+', ຍູ້ອົງປະກອບທີ່ ເທິງສຸດຂອງ stack ໃນ stack ຕົວຂອງມັນເອງ.
  6. ຫລັງຈາກນັ້ນ, ໃຫ້ກວດເບິ່ງວ່າຕົວລະຄອນທີ່ດັດສະນີປັດຈຸບັນໃນສະຕິງທີ່ມອບໃຫ້ເທົ່າກັບ ')', ປ້ອນອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack.
  7. ອື່ນປັບປຸງສາຍສະແດງຜົນທີ່ດັດຊະນີ + 1 ເປັນຕົວລະຄອນຢູ່ທີ່ດັດຊະນີປັດຈຸບັນໃນສະຕິງທີ່ໃຫ້.

ລະຫັດ

ໂປຣແກຣມ 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

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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ n ແມ່ນຕົວເລກຂອງຕົວອັກສອນໃນສາຍທີ່ລະບຸ. ດັ່ງທີ່ພວກເຮົາສາມາດເຫັນໄດ້ວ່າພວກເຮົາ ກຳ ລັງຜ່ານຜ່າອົງປະກອບຂອງລະບົບປ້ອນຂໍ້ມູນທີ່ໃຫ້. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ເນື່ອງຈາກວ່າພວກເຮົາໃຊ້ພື້ນທີ່ໃນການເກັບຮັກສາຕົວອັກສອນ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ສ້າງສະຕິງ ໃໝ່ ເພື່ອເກັບຮັກສາຜົນຜະລິດຄວາມສັບສົນຂອງພື້ນທີ່ຍັງເປັນເສັ້ນ.