Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में "THE" से न खत्म होने वाली स्ट्रिंग्स के लिए DFA


डिटरमिनिस्टिक फाइनाइट ऑटोमेटन (DFA) का उपयोग उन स्ट्रिंग्स को खोजने के लिए करें जो उपस्ट्रिंग "THE" से खत्म नहीं होतीं। हमें ध्यान रखना चाहिए कि उपस्ट्रिंग "THE" की कोई भी विविधता जैसे "tHe", "The", "ThE" आदि स्ट्रिंग के अंत में नहीं होनी चाहिए।

पहले, हम अपने dfa वेरिएबल को परिभाषित करते हैं और इसे 0 से इनिशियलाइज़ करते हैं जो हमारी स्थिति को ट्रैक करता है। यह प्रत्येक कैरेक्टर मिलान पर बढ़ाया जाता है।

int dfa = 0;

begin(char c) मेथड एक कैरेक्टर लेता है और जांचता है कि क्या यह 't' या 'T' है और पहली स्थिति यानी 1 पर जाता है।

void begin(char c){ 
    if (c == 't' || c == 'T') 
        dfa = 1; 
}

firstState(char c) मेथड पहले कैरेक्टर की जांच करता है और उस मान के आधार पर dfa असाइन करता है। यदि c 't' या 'T' है तो हम पहली स्थिति पर जाते हैं, अन्यथा यदि c 'h' या 'H' है तो हम दूसरी स्थिति पर जाते हैं और अंत में यदि यह कोई अन्य कैरेक्टर है तो हम शुरुआती स्थिति यानी 0 पर जाते हैं।

void firstState(char c){ 
    if (c == 't' || c == 'T') 
        dfa = 1; 
    else if (c == 'h' || c == 'H') 
        dfa = 2; 
    else 
        dfa = 0; 
}

secondState(char c) एक कैरेक्टर लेता है और DFA की दूसरी स्थिति की जांच के लिए उपयोग किया जाता है। यदि पास किया गया कैरेक्टर 'E' या 'e' के बराबर है तो हम तीसरी स्थिति पर जाते हैं अन्यथा शुरुआती स्थिति यानी 0 पर।

void secondState(char c){ 
    if (c == 'e' || c == 'E') 
        dfa = 3; 
    else 
        dfa = 0; 
}

thirdState(char c) एक कैरेक्टर लेता है और DFA की तीसरी स्थिति की जांच के लिए उपयोग किया जाता है। यदि कैरेक्टर 't' या 'T' के बराबर है तो हम पहली स्थिति (1) पर जाते हैं अन्यथा शुरुआती स्थिति यानी 0 पर।

void thirdState(char c){ 
    if (c == 't' || c == 'T') 
        dfa = 1; 
    else 
        dfa = 0; 
}

isAccepted(string str) टेस्ट की जाने वाली स्ट्रिंग को पैरामीटर के रूप में लेता है। len वेरिएबल स्ट्रिंग की लंबाई संग्रहीत करता है। फॉर लूप स्ट्रिंग लंबाई तक पुनरावृति करता है। यदि dfa = 0 तो start(char c) फंक्शन कॉल किया जाता है, यदि dfa 1 के बराबर है तो firstState(char c) फंक्शन कॉल किया जाता है और यदि dfa 2 के बराबर है तो secondState(char c) फंक्शन कॉल किया जाता है और यदि dfa 1,2,3 नहीं है तो thirdState(char c) फंक्शन कॉल किया जाता है। हम इस आधार पर सत्य या असत्य वापस करते हैं कि dfa 3 है या नहीं। यदि dfa 3 के बराबर नहीं है तो स्ट्रिंग स्वीकार की जाती है अन्यथा नहीं।

bool isAccepted(string str){ 
    int len = str.length(); 
    for (int i = 0; i < len; i++) { 
        if (dfa == 0) 
            begin(str[i]); 
        else if (dfa == 1) 
            firstState(str[i]); 
        else if (dfa == 2) 
            secondState(str[i]); 
        else 
            thirdState(str[i]); 
    } 
    return (dfa != 3); 
}

उदाहरण

"THE" से न खत्म होने वाली स्ट्रिंग्स के लिए DFA खोजने के लिए निम्नलिखित कार्यान्वयन देखें:

#include <iostream> 
#include <string> 
using namespace std; 

int dfa = 0; 

void begin(char c){ 
    if (c == 't' || c == 'T') 
        dfa = 1; 
} 

void firstState(char c){ 
    if (c == 't' || c == 'T') 
        dfa = 1; 
    else if (c == 'h' || c == 'H') 
        dfa = 2; 
    else 
        dfa = 0; 
} 

void secondState(char c){ 
    if (c == 'e' || c == 'E') 
        dfa = 3; 
    else 
        dfa = 0; 
} 

void thirdState(char c){ 
    if (c == 't' || c == 'T') 
        dfa = 1; 
    else 
        dfa = 0; 
} 

bool isAccepted(string str){ 
    int len = str.length(); 
    for (int i = 0; i < len; i++) { 
        if (dfa == 0) 
            begin(str[i]); 
        else if (dfa == 1) 
            firstState(str[i]); 
        else if (dfa == 2) 
            secondState(str[i]); 
        else 
            thirdState(str[i]); 
    } 
    return (dfa != 3); 
} 

int main(){ 
    string str = "helloForTheWorld"; 
    if (isAccepted(str) == true) 
        cout<<"The string "<<str<<" is accepted "; 
    else 
        cout<<"The string "<<str<<" is not accepted"; 
    return 0; 
}

आउटपुट

उपरोक्त कोड निम्नलिखित आउटपुट देगा:

The string helloForTheWorld is accepted

  1. C++ में जांचें कि पेज को कोण द्वारा घुमाना संभव है या नहीं C++ में जांचें कि पेज को कोण द्वारा घुमाना संभव है या नहीं

    इस समस्या में, हमें एक पेज पर स्थित तीन बिंदुओं के निर्देशांक दिए गए हैं। हमारा कार्य जांचना है कि पेज को कोण द्वारा घुमाना संभव है या नहीं। पेज का घुमाव इस तरह किया जाता है कि x की नई स्थिति y की पुरानी स्थिति है, y की नई स्थिति z की पुरानी स्थिति है। और घुमाव के आधार पर हां या नहीं प्रिंट करें। स

  1. C++ में सभी सबसे गहरे नोड्स वाला सबसे छोटा सबट्री C++ में सभी सबसे गहरे नोड्स वाला सबसे छोटा सबट्री

    मान लीजिए हमारे पास रूट पर रूटेड एक बाइनरी ट्री है, प्रत्येक नोड की गहराई रूट से सबसे छोटी दूरी है। यहां एक नोड सबसे गहरा है यदि इसकी गहराई पूरे ट्री में किसी भी नोड के बीच सबसे बड़ी संभव है। एक नोड का सबट्री वह नोड है, साथ ही उस नोड के सभी वंशजों का सेट। हमें सबसे बड़ी गहराई वाला नोड ढूंढना है जैसे

  1. - विंडोज पर C++ के लिए शीर्ष IDE

    बड़े प्रोजेक्ट्स को केवल टेक्स्ट एडिटर्स पर प्रबंधित करना मुश्किल होता है। ऐसे मामलों में IDE का उपयोग करने से आप अधिक उत्पादक और कम निराश होंगे। विभिन्न प्रकार के IDE उपलब्ध हैं और आपको अपनी आवश्यकताओं के अनुरूप सही चुनना चाहिए। यहां विंडोज के लिए सर्वश्रेष्ठ C/C++ IDEs की सूची दी गई है। Visual S