प्रतिस्थापन के साथ सी ++ संतुलित अभिव्यक्ति

कोष्ठकों का एक संतुलित व्यंजक एक ऐसा व्यंजक है जिसमें सभी प्रकार के कोष्ठकों के जोड़े एक साथ सही क्रम में होते हैं। इसका अर्थ यह है कि प्रत्येक प्रारंभिक कोष्ठक के लिए कोष्ठकों के उचित क्रम में एक समापन कोष्ठक होता है अर्थात { }।

आइए अवधारणा को बेहतर ढंग से समझने के लिए कुछ उदाहरण लेते हैं -

अभिव्यक्ति - {([][]{})({}[]{})}

आउटपुट - संतुलित

स्पष्टीकरण - हम देख सकते हैं कि प्रत्येक प्रारंभिक कोष्ठक के लिए एक समापन कोष्ठक होता है। सभी कोष्ठक एक प्रारंभिक कोष्ठक और जोड़े में समापन कोष्ठक के बीच स्थित हैं।

आउटपुट - बैलेंस नहीं

स्पष्टीकरण - कोष्ठकों के कुछ अव्यवस्थित जोड़े हैं जो व्यंजक को असंतुलित करते हैं।

इस समस्या में प्रतिस्थापन के साथ संतुलन अभिव्यक्ति . कहा जाता है , हमें एक स्ट्रिंग दी गई है जिसमें इन कोष्ठकों '{' , '}' , '[' , ']' , '(' , ')' का व्यंजक है। कुछ स्थान ऐसे हैं जहाँ कोष्ठक गायब हैं और इसके स्थान पर "*" रखा गया है। और हमें यह जांचना होगा कि सभी तारांकन चिह्नों को उपयुक्त कोष्ठकों से बदलने पर क्या दिया गया व्यंजक एक मान्य व्यंजक बन सकता है।

उदाहरण

इनपुट - क्स्प ="{[*(*)]}"

आउटपुट − व्यंजक संतुलित किया जा सकता है

स्पष्टीकरण - दो प्रतीक हैं जिन्हें प्रतिस्थापित करने की आवश्यकता है। और प्रतिस्थापन पर {[(())]}

इनपुट - क्स्प ="[(*){}{{}}]"

आउटपुट − व्यंजक संतुलित नहीं हो सकता

स्पष्टीकरण - एक प्रतीक है जिसे बदलने की जरूरत है। और * को किसी भी कोष्ठक से बदलने पर व्यंजक संतुलित नहीं हो सकता।

अब चूंकि हमें समस्या की स्पष्ट समझ है, इसलिए हम इस समस्या का समाधान तैयार कर सकते हैं। यह जांचने के लिए कि दी गई कोष्ठक अभिव्यक्ति संतुलित होगी या नहीं, हम अपने कार्यों को करने के लिए स्टैक डेटा संरचना का उपयोग करेंगे।

इस कार्य को पूरा करने के लिए किए जाने वाले ऑपरेशन हैं -

• स्ट्रिंग एक्सप्रेशन के प्रत्येक तत्व को ट्रैवर्स करें और −

  . करें

• जब एक्सप्रेशन यानी '{' , '[' , '(' ) में एक ओपनिंग ब्रैकेट मिलता है, तो स्टैक में एलिमेंट को पुश करें।

• जब व्यंजक यानी '}' , ']' , ')' में एक क्लोजिंग ब्रैकेट मिलता है। तत्व को स्टैक के शीर्ष पर पॉप करें और जांचें कि क्या यह सामना किए गए समापन ब्रैकेट के लिए मेल खाने वाला उद्घाटन है।

  • यदि दोनों कोष्ठक मेल खाते हैं, तो व्यंजक के अगले तत्व (चरण 1) पर जाएँ।

  • यदि दोनों कोष्ठक मेल नहीं खाते, तो व्यंजक संतुलित नहीं है।

• जब व्यंजक में एक * का सामना करना पड़ता है जो एक उद्घाटन के साथ-साथ समापन कोष्ठक भी हो सकता है। फिर,

  • पहले इसे ओपनिंग ब्रैकेट के रूप में मानें और इसे स्टैक में पुश करें और अगले एलिमेंट के लिए रिकर्सिव कॉल का उपयोग करके मैचिंग क्लोजिंग ब्रैकेट खोजें। यदि इसका परिणाम फ़ैसले में होता है, तो अगले चरण का पालन करें

  • इसे क्लोजिंग ब्रैकेट के रूप में मानें, इसे स्टैक के शीर्ष से मेल खाना चाहिए और फिर स्टैक के शीर्ष को पॉप करना चाहिए।

  • यह * का समापन मूल्य संतुलित नहीं शुरुआती रिटर्न से मेल नहीं खाता।

• परिणाम के आधार पर स्टेटमेंट प्रिंट करें।

उदाहरण

इस समाधान के आधार पर एक प्रोग्राम बनाते हैं

#include <bits/stdc++.h>
using namespace std;
int isMatching(char a, char b){
   if ((a == '{' &amp; b == '}') || (a == '[' &amp; b == ']') || (a == '(' &amp; b == ')') || a == '*')
      return 1;
   return 0;
}
int isBalancedexpression(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 isBalancedexpression(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 isBalancedexpression(s, ele, ind + 1);
   }
   else if (s[ind] == '*') {
      stack<char> tmp = ele;
      tmp.push(s[ind]);
      res = isBalancedexpression(s, tmp, ind + 1);
      if (res)
         return 1;
      if (ele.empty())
         return 0;
      ele.pop();
      return isBalancedexpression(s, ele, ind + 1);
   }
}
int main(){
   string s = "{[*(*)]}";
   stack ele;
   if (isBalancedexpression(s, ele, 0))
      cout << "Balanced";
   else
      cout << "Not Balanced";
   return 0;
}

आउटपुट

Balanced