ពិនិត្យវង់ក្រចកដែលមានតុល្យភាពនៅក្នុងឃ្លាមួយ  


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

ដែលបានផ្តល់ឱ្យ ខ្សែអក្សរ s នៃប្រវែង n ។ ពិនិត្យមើលថាតើមានវង់ក្រចកបិទសម្រាប់វង់ក្រចកបើកទាំងអស់ដែរឬទេ។ ប្រសិនបើវង់ក្រចកទាំងអស់មានតុល្យភាព។ និយាយម៉្យាងទៀតយើងក៏អាចនិយាយបានដែរថាប្រសិនបើយើងមាន '}', ')' និង ']' សម្រាប់រាល់ '{', '(' និង '[' រៀងៗខ្លួន, ការបញ្ចេញមតិត្រូវបានគេនិយាយថាមានតុល្យភាព។

ឧទាហរណ៍ -

ឃ្លា“ {[()]}” មានវង់ក្រចកដែលមានតុល្យភាពពីព្រោះវាមានវង់ក្រចកបិទសម្រាប់វង់ក្រចកបើក។

ពិនិត្យវង់ក្រចកដែលមានតុល្យភាពនៅក្នុងឃ្លាមួយពិន

ឧទាហរណ៍  

បញ្ចូល: s =“ [()] {} {[() ()] ()}”

លទ្ធផល: ការបញ្ចេញមតិមានតុល្យភាព។

បញ្ចូល: s =“ [() {}”

លទ្ធផល: ការបញ្ចេញមតិមិនមានតុល្យភាពទេ។

វិធីសាស្រ្ត  

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

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

  1. ចាប់ផ្តើមខ្សែអក្សរដែលមានប្រវែង n ។
  2. បង្កើត ជង់ ដើម្បីទុកតួអក្សរ។
  3. ឆ្លងកាត់ខ្សែអក្សរហើយពិនិត្យមើលថាតើចរិតបច្ចុប្បន្នគឺជាវង់ក្រចកបើករុញវានៅក្នុងជង់ហើយបន្ត។
  4. ប្រសិនបើជង់ទទេត្រលប់មកវិញមិនពិត។
  5. ប្តូរវង់ក្រចកបិទហើយពិនិត្យមើលថាតើតួអក្សរនៅខាងលើជង់គឺជាវង់ក្រចកបើកមានប្រភេទដូចគ្នានឹងវង់ក្រចកបិទតួអក្សរខាងលើនិងបំបែក។ អ្នកផ្សេងត្រឡប់មកវិញមិនពិត។
  6. ប្រសិនបើជង់វិលត្រលប់មកវិញជាការពិតអ្វីៗផ្សេងទៀតមិនពិតទេ។
សូម​មើល​ផង​ដែរ
តាមដានធាតុអតិបរិមាបច្ចុប្បន្ននៅក្នុងជង់

កម្មវិធី C ++ ដើម្បីពិនិត្យវង់ក្រចកដែលមានតុល្យភាពនៅក្នុងកន្សោមមួយ  

#include<bits/stdc++.h> 
using namespace std; 
  
bool isBalanced(string str){ 
    stack<char> s; 
    char x; 
  
    for(int i=0; i<str.length(); i++){ 
        if(str[i]=='('||str[i]=='['||str[i]=='{'){ 
            s.push(str[i]); 
            continue; 
        }
  
        if(s.empty()) 
           return false; 
  
        switch(str[i]){ 
            case ')': 
      
                x = s.top(); 
                s.pop(); 
                if(x=='{' || x=='[') 
                    return false; 
                break; 
      
            case '}': 
      
                x = s.top(); 
                s.pop(); 
                if(x=='(' || x=='[') 
                    return false; 
                break; 
      
            case ']': 
      
                x = s.top(); 
                s.pop(); 
                if(x =='(' || x == '{') 
                    return false; 
                break; 
        } 
    } 
  
    return (s.empty()); 
} 
  
int main(){ 
    string s = "[()]{}{[()()]()}"; 
  
    if(isBalanced(s)){ 
        cout<<"Expression is balanced."; 
    }    
    else{
        cout<<"Expression is not balanced."; 
    }    
    return 0; 
}
Expression is balanced.

កម្មវិធីចាវ៉ាដើម្បីពិនិត្យមើលវង់ក្រចកដែលមានតុល្យភាពនៅក្នុងកន្សោមមួយ  

class Parantheses{ 
    
    static class stack{ 
        int top=-1; 
        char items[] = new char[100]; 
        
        void push(char x){ 
            if(top == 99){ 
                System.out.println("Stack full"); 
            }  
            
            else{ 
                items[++top] = x; 
            } 
        } 
    
        char pop(){ 
            if(top == -1){ 
                System.out.println("Underflow error"); 
                return '\0'; 
            }  
            
            else{ 
                char element = items[top]; 
                top--; 
                return element; 
            } 
        } 
    
        boolean isEmpty(){ 
            return (top == -1) ? true : false; 
        } 
    } 
    
    static boolean isPair(char character1, char character2){ 
        if(character1 == '(' && character2 == ')') 
            return true; 
        
        else if(character1 == '{' && character2 == '}') 
            return true; 
        
        else if(character1 == '[' && character2 == ']') 
            return true; 
        
        else
            return false; 
    } 
    
    static boolean isBalanced(char s[]){ 
        stack st=new stack(); 
        
        for(int i=0;i<s.length;i++){ 
        
            if(s[i] == '{' || s[i] == '(' || s[i] == '[') 
                st.push(s[i]); 
            
            if(s[i] == '}' || s[i] == ')' || s[i] == ']'){ 
            
                if (st.isEmpty()){ 
                    return false; 
                }  
                
                else if( !isPair(st.pop(), s[i])){ 
                    return false; 
                } 
            } 
        
        } 
        
        if(st.isEmpty()) 
            return true;
            
        else
            return false; 
    }  
    
    public static void main(String[] args){ 
        char s[] = {'[','(',')',']','{','}','{','[','(',')','(',')',']','(',')','}'}; 
        
        if(isBalanced(s)){ 
            System.out.println("Expression is balanced.");
        }    
        
        else{
            System.out.println("Expression is not balanced.");   
        }
    } 
}
Expression is balanced.

ការវិភាគស្មុគស្មាញសម្រាប់វង់ក្រចកដែលមានតុល្យភាពនៅក្នុងកន្សោមមួយ  

ស្មុគស្មាញពេលវេលា៖ O (n) ដែល n ជាចំនួនវង់ក្រចក / តួអក្សរនៅក្នុងខ្សែអក្សរដែលបានផ្តល់។

សូម​មើល​ផង​ដែរ
ទាយពាក្យ

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

ឯកសារយោង