அடைப்புக்குறிகளுடன் இரண்டு வெளிப்பாடுகள் ஒரே மாதிரியாக இருக்கிறதா என்று சோதிக்கவும்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் உயர்வு ஆரக்கிள் Snapdeal வால்மார்ட் ஆய்வகங்கள் விப்ரோ யாத்ரா ஸோகோ
ஸ்டேக் சரம்

கூட்டல் ஆபரேட்டர், கழித்தல் ஆபரேட்டர், சிற்றெழுத்து எழுத்துக்கள் மற்றும் அடைப்புக்குறிப்பு ஆகியவற்றைக் கொண்ட வெளிப்பாடுகளைக் குறிக்கும் இரண்டு சரங்களை s1 மற்றும் s2 கொடுக்கப்பட்டுள்ளது. அடைப்புக்குறிகளுடன் இரண்டு வெளிப்பாடுகள் ஒரே மாதிரியாக இருக்கிறதா என்று சோதிக்கவும்.

அடைப்புக்குறிகளுடன் இரண்டு வெளிப்பாடுகள் ஒரே மாதிரியாக இருக்கிறதா என்று சோதிக்கவும்

உதாரணமாக

உள்ளீடு 

s1 = “- (a + b + c)”

s2 = “-abc”

வெளியீடு 

ஆம்

உள்ளீடு 

s1 = “ab- (cd)”

s2 = “abcd”

வெளியீடு

இல்லை

அடைப்புக்குறிகளுடன் இரண்டு வெளிப்பாடுகள் ஒரே மாதிரியாக இருக்கிறதா என்று சோதிக்க வழிமுறை

  1. இரண்டைத் தொடங்கவும் சரங்களை கூட்டல் ஆபரேட்டர், கழித்தல்_ஆப்பரேட்டர், சிற்றெழுத்து எழுத்துக்கள் மற்றும் அடைப்புக்குறி ஆகியவற்றைக் கொண்ட s1 மற்றும் s2 பிரதிநிதித்துவ_எக்ஸ்பிரஷன்கள்.
  2. ஒரு திசையனை உருவாக்கி, திசையனின் அனைத்து மதிப்புகளையும் 0 ஆக துவக்கவும்.
  3. அதன் பிறகு பூலியன் வகையின் ஒரு அடுக்கை உருவாக்கி அதில் உண்மையைத் தள்ளுங்கள்.
  4. சரம் 1 அதாவது எஸ் 1 வழியாக பயணிக்கவும், சரத்தின் தற்போதைய குறியீட்டில் உள்ள எழுத்து '+' அல்லது '-' க்கு சமமாக இருக்கிறதா என்று சரிபார்க்கவும், அடுத்த மறு செய்கைக்குச் செல்லவும்.
  5. சரத்தின் தற்போதைய குறியீட்டில் உள்ள எழுத்து திறப்பு அடைப்புக்கு சமமாக இருந்தால், சரத்தின் முந்தைய குறியீட்டில் உள்ள எழுத்து '-' க்கு சமமாக இல்லையா என்பதைச் சரிபார்க்கவும், அடுக்கின் மேலே உள்ள மதிப்பை அடுக்கில் தள்ளுங்கள் அடுக்கின் மேல் உள்ள மதிப்பின் மதிப்பை அழுத்துங்கள்.
  6. 5 படி சரிபார்க்கவில்லை என்றால், சரத்தின் தற்போதைய குறியீட்டில் உள்ள எழுத்து ஒரு மூடு அடைப்புக்கு சமமாக இருந்தால், அடுக்கை மேலே உள்ள உறுப்பை பாப் செய்யவும்.
  7. அடுக்கில் மேல் இருக்கிறதா என சரிபார்க்கவும், திசையனை v [s1 [i] - 'a'] + = (adjSign (s1, i)? Add? 1: -1: add? -1: 1) என புதுப்பிக்கவும் திசையன் v [s1 [i] - 'a'] + = (adjSign (s1, i)? சேர்? -1: 1: சேர்? 1: -1).
  8. இதேபோல், அதே படிகளை சரம் 2 அதாவது s2 உடன் மீண்டும் செய்யவும்.
  9. அதன்பிறகு, 0 முதல் 25 வரை பயணித்து, திசையனின் தற்போதைய குறியீட்டின் மதிப்பு 0 க்கு சமமாக இல்லாவிட்டால் சரிபார்க்கவும், “இல்லை” என அச்சிடுங்கள் “ஆம்” என்று அச்சிடவும்.

அடைப்புகளுடன் இரண்டு வெளிப்பாடுகள் ஒரே மாதிரியாக இருக்கிறதா என்று சோதிக்க சி ++ நிரல்

#include <bits/stdc++.h> 
using namespace std; 
  
const int MAX_CHAR = 26; 
  
bool adjSign(string s, int i){ 
    if(i == 0){ 
        return true;
    }
    
    if(s[i - 1] == '-'){ 
        return false; 
    }
    
    return true; 
}; 
  
void eval(string s, vector<int>& v, bool add){ 
    stack<bool> stk; 
    stk.push(true); 
  
    int i = 0; 
    while(s[i] != '\0'){ 
        if(s[i] == '+' || s[i] == '-'){ 
            i++; 
            continue; 
        } 
        
        if(s[i] == '('){ 
            if(adjSign(s, i)){  
                stk.push(stk.top());
            }
            else{ 
                stk.push(!stk.top()); 
            }
        } 
  
        else if(s[i] == ')'){  
            stk.pop(); 
        }
          
        else{ 
            if(stk.top()){                  
                v[s[i] - 'a'] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); 
            }
  
            else{                 
                v[s[i] - 'a'] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); 
            }
        } 
        i++; 
    } 
}; 
  
bool areSame(string s1, string s2){ 
    vector<int> v(MAX_CHAR, 0); 
  
    eval(s1, v, true); 
  
    eval(s2, v, false); 
  
    for(int i = 0; i < MAX_CHAR; i++){ 
        if(v[i] != 0){  
            return false;
        }
    }
  
    return true; 
} 
  
int main(){ 
    string s1 = "-(a+b+c)", s2 = "-a-b-c"; 
    
    if(areSame(s1, s2)){ 
        cout << "Yes\n"; 
    }
    else{
        cout << "No\n"; 
    }
    
    return 0; 
}
Yes

அடைப்புக்குறிகளுடன் இரண்டு வெளிப்பாடுகள் ஒரே மாதிரியாக இருக்கிறதா என்று சோதிக்க ஜாவா நிரல்

import java.io.*; 
import java.util.*; 
  
class CheckExpressions{ 
  
    static final int MAX_CHAR = 26; 
  
    static boolean adjSign(String s, int i){ 
        if(i == 0){ 
            return true;
        }
        
        if(s.charAt(i - 1) == '-'){ 
            return false; 
        }
        
        return true; 
    }; 
  
    static void eval(String s, int[] v, boolean add){ 
  
        Stack<Boolean> stk = new Stack<>(); 
        stk.push(true); 
  
        int i = 0; 
        while(i < s.length()){ 
            if(s.charAt(i) == '+' || s.charAt(i) == '-'){ 
                i++; 
                continue; 
            } 
            
            if(s.charAt(i) == '('){ 
                if(adjSign(s, i)){ 
                    stk.push(stk.peek());
                }
                
                else{
                    stk.push(!stk.peek()); 
                }
            } 
  
            else if(s.charAt(i) == ')'){ 
                stk.pop(); 
            }
  
            else{ 
                if(stk.peek()){ 
                    v[s.charAt(i) - 'a'] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); 
                }
  
                else{
                    v[s.charAt(i) - 'a'] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); 
                }
            } 
            i++; 
        } 
    }; 
  
    static boolean areSame(String s1, String s2){ 
  
        int[] v = new int[MAX_CHAR]; 
  
        eval(s1, v, true); 
  
        eval(s2, v, false); 
  
        for(int i = 0; i < MAX_CHAR; i++){ 
            if(v[i] != 0){ 
                return false; 
            }
        }
  
        return true; 
    } 
  
    public static void main(String[] args){ 
  
        String s1 = "-(a+b+c)", s2 = "-a-b-c"; 
        
        if(areSame(s1, s2)){ 
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    } 
}
Yes

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது: O (அதிகபட்சம் (n1, n2)), அங்கு n1 மற்றும் n2 ஆகியவை முறையே கொடுக்கப்பட்ட சரங்களின் நீளம் s1 மற்றும் s2 ஆகும்.

விண்வெளி சிக்கலானது: ஓ (அதிகபட்சம் (n1, n2)) ஏனெனில் கொடுக்கப்பட்ட சரங்களின் எழுத்துக்களை சேமிக்க இடத்தைப் பயன்படுத்தினோம்.

குறிப்புகள்