প্রতিস্থাপন সহ C++ ভারসাম্যপূর্ণ অভিব্যক্তি

বন্ধনীর একটি ভারসাম্যপূর্ণ অভিব্যক্তি হল এমন একটি অভিব্যক্তি যা সঠিক ক্রমে সব ধরণের বন্ধনীর জোড়া একত্রে ধারণ করে। এর মানে হল যে প্রতিটি খোলা বন্ধনীর জন্য বন্ধনীর যথাযথ ক্রমে একটি বন্ধ বন্ধনী থাকে অর্থাৎ { }।

ধারণাটি আরও ভালোভাবে বোঝার জন্য কয়েকটি উদাহরণ দেওয়া যাক −

অভিব্যক্তি − {([][]{})({}[]{})}

আউটপুট - সুষম

ব্যাখ্যা − আমরা দেখতে পাচ্ছি যে প্রতিটি খোলা বন্ধনীর জন্য একটি বন্ধ বন্ধনী রয়েছে। জোড়ায় খোলা বন্ধনী এবং বন্ধ বন্ধনীর মধ্যে থাকা সমস্ত বন্ধনী।

আউটপুট - ভারসাম্য নয়

ব্যাখ্যা − কিছু অবিন্যস্ত জোড়া বন্ধনী রয়েছে যা অভিব্যক্তিটিকে ভারসাম্যহীন করে তোলে।

এই সমস্যাটিতে বলা হয় প্রতিস্থাপন সহ অভিব্যক্তির ভারসাম্য , আমাদের একটি স্ট্রিং দেওয়া হয়েছে যাতে এই বন্ধনীগুলির একটি অভিব্যক্তি রয়েছে ‘{’, ‘}’, ‘[’, ‘]’, ‘(’, ‘)’। কিছু জায়গা আছে যেখানে বন্ধনী অনুপস্থিত এবং এর পরিবর্তে "*" বসানো হয়েছে। এবং আমাদের পরীক্ষা করতে হবে যে উপযুক্ত বন্ধনী দিয়ে সমস্ত তারকাচিহ্নের চিহ্নগুলি প্রতিস্থাপন করার সময় প্রদত্ত অভিব্যক্তিটি একটি বৈধ অভিব্যক্তি হতে সক্ষম হতে পারে।

উদাহরণ

ইনপুট − exp =“{[*(*)]}”

আউটপুট - অভিব্যক্তিটি ভারসাম্যপূর্ণ হতে পারে

ব্যাখ্যা - দুটি চিহ্ন রয়েছে যা প্রতিস্থাপন করা দরকার। এবং প্রতিস্থাপন হলে {[(())]}

ইনপুট − exp =“[(*){}{{}}]”

আউটপুট - অভিব্যক্তিটি ভারসাম্যপূর্ণ হতে পারে না

ব্যাখ্যা - একটি প্রতীক আছে যা প্রতিস্থাপন করা প্রয়োজন। এবং কোন বন্ধনীর সাথে * এর প্রতিস্থাপনে অভিব্যক্তিটি ভারসাম্যপূর্ণ হতে পারে না।

এখন যেহেতু আমরা সমস্যাটি পরিষ্কারভাবে বুঝতে পেরেছি, আমরা এই সমস্যার জন্য একটি সমাধান তৈরি করতে পারি। প্রদত্ত বন্ধনী অভিব্যক্তি ভারসাম্যপূর্ণ হবে কিনা তা পরীক্ষা করতে আমরা আমাদের কাজগুলি সম্পাদন করতে স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করব।

এই কাজটি সম্পন্ন করার জন্য যে অপারেশনগুলি করা হয় তা হল −

• স্ট্রিং এক্সপ্রেশনের প্রতিটি উপাদান অতিক্রম করুন এবং করুন −

• যখন অভিব্যক্তিতে একটি খোলা বন্ধনী সম্মুখীন হয় যেমন ‘{’ , ‘[’ , ‘(’ , উপাদানটিকে স্ট্যাকের মধ্যে পুশ করুন।

• যখন একটি ক্লোজিং ব্র্যাকেট অভিব্যক্তিতে সম্মুখীন হয় যেমন ‘}’, ‘]’, ‘)’। স্ট্যাকের শীর্ষে উপাদানটি পপ করুন এবং এটি সম্মুখীন বন্ধনী বন্ধনীর জন্য একটি ম্যাচিং ওপেনিং কিনা তা পরীক্ষা করুন৷

  • যদি উভয় বন্ধনী মিলে যায়, তাহলে অভিব্যক্তির পরবর্তী উপাদানে যান (ধাপ 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