កន្សោមដែលមានតុល្យភាពជាមួយនឹងការជំនួស  


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ការដំឡើង ក្រុមហ៊ុន Oracle Snapchat Snapdeal បន្ទប់ពិសោធន៍វ៉លម៉ាត Wipro Yatra Zoho
ជង់ ខ្សែអក្សរ

នៅក្នុងការបង្ហាញប្រកបដោយតុល្យភាពជាមួយនឹងបញ្ហាការជំនួសយើងបានផ្តល់ខ្សែអក្សរដែលមានវង់ក្រចកពោលគឺ '(', ')', '[', ']', '{', '}' ។ នេះ ខ្សែអក្សរ ក៏មាន x នៅកន្លែងខ្លះជាការជំនួសវង់ក្រចក។ ពិនិត្យមើលថាតើខ្សែអក្សរអាចត្រូវបានបំលែងទៅជាកន្សោមជាមួយនឹងវង់ក្រចកត្រឹមត្រូវបន្ទាប់ពីការជំនួសរបស់ x ទាំងអស់ជាមួយវង់ក្រចកណាមួយ។

កន្សោមដែលមានតុល្យភាពជាមួយនឹងការជំនួសពិន

ឧទាហរណ៍  

បញ្ចូល 

s =“ {(x [x])}”

ទិន្នផល

 បាទ

បញ្ចូល

s =“ [{x} (x)]”

ទិន្នផល 

ទេ

ក្បួនដោះស្រាយ  

ឥឡូវនេះយើងដឹងពីសេចក្តីថ្លែងការណ៍បញ្ហានៃការបង្ហាញតុល្យភាពជាមួយនឹងបញ្ហាការជំនួស។ ដូច្នេះយើងមករកក្បួនដោះស្រាយខាងក្រោមដើម្បីរកដំណោះស្រាយ។

  1. ចាប់ផ្តើមខ្សែអក្សរ s, ជង់នៃប្រភេទតួអក្សរនិងអថេរដើម្បីរក្សាទុកលិបិក្រមបច្ចុប្បន្ន ០ ។
  2. ប្រសិនបើប្រវែងនៃខ្សែគឺស្មើនឹងសន្ទស្សន៍បច្ចុប្បន្នត្រឡប់ 1 ប្រសិនបើជង់ទទេផ្សេងទៀត 0 ។
  3. ពិនិត្យមើលថាតើតួអក្សរនៅលិបិក្រមបច្ចុប្បន្ននៅក្នុងខ្សែអក្សរគឺជាវង់ក្រចកបើករុញវានៅក្នុងជង់ហើយត្រឡប់ការហៅឡើងវិញជាមួយសន្ទស្សន៍បច្ចុប្បន្នជាសន្ទស្សន៍បច្ចុប្បន្ន + 1 ។
  4. ផ្សេងទៀតប្រសិនបើតួអក្សរនៅសន្ទស្សន៍បច្ចុប្បន្ននៅក្នុងខ្សែអក្សរគឺជាវង់ក្រចកបិទ, ពិនិត្យមើលថាតើជង់វិលត្រឡប់មកវិញទទេ 0 ផ្សេងទៀតពិនិត្យមើលប្រសិនបើកំពូលនៃជង់មិនស្មើនឹងវង់ក្រចកបើកទៅតួអក្សរបច្ចុប្បន្ននៅក្នុងខ្សែអក្សរត្រឡប់ 0 ។ បញ្ចូលនិងហៅត្រឡប់មកវិញដោយប្រើសន្ទស្សន៍បច្ចុប្បន្នជាសន្ទស្សន៍បច្ចុប្បន្ន + ១ ។
  5. ក្រៅពីប្រសិនបើតួអក្សរនៅលិបិក្រមបច្ចុប្បន្ននៅក្នុងខ្សែគឺស្មើនឹង x បង្កើតជង់បណ្តោះអាសន្នស្មើនឹងលេខចាស់ហើយរុញតួអក្សរចូល។
  6. បង្កើតអថេរអថេរ។ ធ្វើការហៅឡើងវិញជាមួយសន្ទស្សន៍បច្ចុប្បន្នជាសន្ទស្សន៍បច្ចុប្បន្ន + ១ និងជង់បណ្តោះអាសន្ន។ រក្សាទុកលទ្ធផលរបស់វានៅក្នុង res ។
  7. ប្រសិនបើ res ស្មើនឹង ១ ត្រឡប់ ១ ។
  8. ប្រសិនបើជង់ចាស់ទំនេរត្រឡប់ 0 ។
  9. បញ្ចូលផ្នែកខាងលើពីជង់ចាស់ហើយត្រឡប់ការហៅម្តងទៀតជាមួយសន្ទស្សន៍បច្ចុប្បន្នជាសន្ទស្សន៍បច្ចុប្បន្ន +1 និងជង់ចាស់។
សូម​មើល​ផង​ដែរ
ផលិតផលអតិបរិមានៃសន្ទស្សន៍បន្ទាប់ធំជាងនៅខាងឆ្វេងនិងខាងស្តាំ

កម្មវិធី C ++ សម្រាប់ការបញ្ចេញមតិប្រកបដោយតុល្យភាពជាមួយនឹងការជំនួស  

#include <bits/stdc++.h> 
using namespace std; 
  
int isMatching(char a, char b){ 
    if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x') 
      return 1; 
    return 0; 
} 
  
int isBalanced(string s, stack<char> ele, int ind){ 
  
    if(ind == s.length()){  
        return ele.empty();
    }
  
    char topEle; 
  
    int res; 
  
    if((s[ind] == '{') || (s[ind] == '(') || (s[ind] == '[')){ 
        ele.push(s[ind]); 
        return isBalanced(s, ele, ind + 1); 
    } 
  
    else if((s[ind] == '}') || (s[ind] == ')') || (s[ind] == ']')){ 
  
        if(ele.empty()){  
            return 0; 
        }
  
        topEle = ele.top(); 
        ele.pop(); 
  
        if(!isMatching(topEle, s[ind])){  
            return 0; 
        }
          
        return isBalanced(s, ele, ind + 1); 
    } 
  
    else if(s[ind] == 'x'){ 
        stack<char> tmp = ele; 
        tmp.push(s[ind]); 
        res = isBalanced(s, tmp, ind + 1); 
        if(res){ 
            return 1;
        }
        if(ele.empty()){ 
            return 0; 
        }
        ele.pop();
        
        return isBalanced(s, ele, ind + 1); 
    } 
} 
  
int main(){ 
    string s = "{(x[x])}"; 
    stack<char> ele;
    
    if(isBalanced(s, ele, 0)){  
        cout<<"Yes";   
    }
    
    else{ 
        cout<<"No";
    }
    return 0; 
}
Yes

កម្មវិធីចាវ៉ាសម្រាប់ការបញ្ចេញមតិប្រកបដោយតុល្យភាពជាមួយនឹងការជំនួស  

import java.util.Stack; 
  
class BalancedExpression{ 
    
    static int isMatching(char a, char b){ 
        if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x'){ 
            return 1; 
        } 
        return 0; 
    } 
  
    static int isBalanced(String s, Stack<Character> ele, int ind){ 
  
        if(ind == s.length()){ 
            if(ele.size() == 0){ 
                return 1; 
            } 
            else{ 
                return 0; 
            } 
        } 
  
        char topEle; 
  
        int res; 
  
        if((s.charAt(ind) == '{') || (s.charAt(ind) == '(') || (s.charAt(ind) == '[')){ 
            ele.push(s.charAt(ind)); 
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if((s.charAt(ind) == '}') || (s.charAt(ind) == ')') || (s.charAt(ind) == ']')){ 
  
            if(ele.size() == 0){ 
                return 0; 
            } 
  
            topEle = ele.peek(); 
            ele.pop(); 
  
            if(isMatching(topEle, s.charAt(ind)) == 0){ 
                return 0; 
            } 
  
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if(s.charAt(ind) == 'x'){ 
            Stack<Character> tmp = new Stack<>(); 
            
            tmp.addAll(ele);  
            tmp.push(s.charAt(ind)); 
            res = isBalanced(s, tmp, ind + 1); 
            
            if(res == 1){ 
                return 1; 
            } 
            
            if(ele.size() == 0){ 
                return 0; 
            } 
            
            ele.pop(); 
            return isBalanced(s, ele, ind + 1); 
        } 
        return 1; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "{(x[x])}"; 
        Stack<Character> ele = new Stack<Character>(); 
  
        if(isBalanced(s, ele, 0) != 0){ 
            System.out.println("Yes"); 
        } 
        
        else{ 
            System.out.println("No"); 
        } 
    } 
}
Yes

ការវិភាគស្មុគស្មាញ  

ស្មុគស្មាញពេលវេលា៖ O ((2 ^ n) * n) ដែល n ជាប្រវែងនៃខ្សែអក្សរ។

សូម​មើល​ផង​ដែរ
ស្វែងរកកំពូលបីម្តងហើយម្តងទៀតនៅក្នុងអារេ

អវកាសជំនួយ: O (n) ពីព្រោះយើងបានប្រើកន្លែងទំនេរបន្ថែមនៅក្នុងជង់។

ឯកសារយោង