C++ প্রোগ্রাম: স্ট্যাক ব্যবহার করে ব্যালেন্সড প্যারেনথেসিস চেক করা

এখানে আমরা আলোচনা করব কীভাবে স্ট্যাক ব্যবহার করে ব্যালেন্সড ব্র্যাকেট চেক করা যায়। আমরা শুধু ওপেনিং এবং ক্লোজিং ব্র্যাকেট চেক করি না, বরং ব্র্যাকেটের অর্ডারও চেক করি। উদাহরণস্বরূপ, এক্সপ্রেশন "[{} () {()}]" সঠিক, কিন্তু "{[}]" সঠিক নয়।

ইনপুট: ব্র্যাকেটসহ এক্সপ্রেশন "{()}[]"
আউটপুট: তারা ব্যালেন্সড

অ্যালগরিদম

স্টেপ ১: ব্র্যাকেট ধারণ করার জন্য একটি স্ট্যাক ডিফাইন করুন
স্টেপ ২: এক্সপ্রেশনটি বাম থেকে ডানে ট্রাভার্স করুন
  স্টেপ ২.১: যদি ক্যারেক্টার ওপেনিং ব্র্যাকেট (, বা { বা [ হয়, তবে সেটি স্টকে পুশ করুন
  স্টেপ ২.২: যদি ক্যারেক্টার ক্লোজিং ব্র্যাকেট ), } বা ] হয়
    তবে স্ট্যাক থেকে পপ করুন, এবং যদি পপ করা ক্যারেক্টার শুরুর ব্র্যাকেটের সাথে মিলে যায় তবে ঠিক আছে। অন্যথায় তারা ব্যালেন্সড নয়।
স্টেপ ৩: ট্রাভার্সাল শেষে যদি স্টকে ওপেনিং ব্র্যাকেট থাকে তবে সেটি ব্যালেন্সড নয়।

উদাহরণ কোড

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

bool isBalanced(string expr) {
    stack<char> s;
    char ch;
    for (int i = 0; i < expr.length(); i++) {
        if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
            s.push(expr[i]);
            continue;
        }
        if (s.empty())
            return false;
        switch (expr[i]) {
            case ')':
                ch = s.top();
                s.pop();
                if (ch == '{' || ch == '[')
                    return false;
                break;
            case '}':
                ch = s.top();
                s.pop();
                if (ch == '(' || ch == '[')
                    return false;
                break;
            case ']':
                ch = s.top();
                s.pop();
                if (ch == '(' || ch == '{')
                    return false;
                break;
        }
    }
    return (s.empty()); // যখন স্ট্যাক খালি, true রিটার্ন
}

main() {
    string expr = "[{}(){()}]";
    if (isBalanced(expr))
        cout << "Balanced";
    else
        cout << "Not Balanced";
}

আউটপুট

Balanced