C++-তে টার্নারি এক্সপ্রেশন ইভ্যালুয়েট করার প্রোগ্রাম

মনে করুন আমাদের কাছে একটি টার্নারি এক্সপ্রেশন (ternary expression) আছে, আমাদের সেটির ফলাফল বের করতে হবে। এই এক্সপ্রেশনটি সমর্থন করে T এবং F (True এবং False জন্য) এবং "?" ও ":" ক্যারেক্টারগুলো। কিছু বৈশিষ্ট্য:

• দেওয়া স্ট্রিংর দৈর্ঘ্য সর্বোচ্চ ১০,০০০ হতে পারে।
• শর্তযুক্ত এক্সপ্রেশনগুলো ডান-থেকে-বাম (right-to-left) গ্রুপ হয়।
• শর্ত (condition) সর্বদা T বা F হবে। শর্ত কখনোই ডিজিট (digit) হবে না।
• এক্সপ্রেশনের ফলাফল সর্বদা T বা F আকারে ইভ্যালুয়েট হবে।

উদাহরণস্বরূপ, যদি ইনপুট হয় "T ? T ? F : T : T", তবে আউটপুট হবে F।

সমাধানের পদ্ধতি

এই সমস্যাটি সমাধানের জন্য আমরা স্ট্যাক (stack) ব্যবহার করব এবং স্ট্রিংটি উল্টে দিক থেকে (right-to-left) প্রসেস করব। কারণ টার্নারি অপারেটর ডান-থেকে-বাম এসোসিয়েটিভ (associative)।

এলগরিদমের ধাপসমূহ:

1. ret := খালি স্ট্রিং, n := s-এর সাইজ।
2. একটি স্ট্যাক st তৈরি করুন।
3. i = n-1 থেকে 0 পর্যন্ত লুপ চালান:
   • x := s[i]
   • যদি স্ট্যাক খালি না হয় এবং স্ট্যাকের টপ '?' হয়:
     • স্ট্যাক থেকে পপ করুন ('?' বাদ দিন)।
     • first := স্ট্যাকের টপ, তারপর স্ট্যাক থেকে দুইটি এলিমেন্ট পপ করুন।
     • second := স্ট্যাকের টপ, তারপর স্ট্যাক থেকে একটি এলিমেন্ট পপ করুন।
     • যদি x == 'T' হয়, তবে first স্ট্যাকে পুশ করুন, অন্যথায় second পুশ করুন।
   • অন্যথায় x স্ট্যাকে পুশ করুন।
4. যখন স্ট্যাক খালি না হয়:
   • ret := ret + স্ট্যাকের টপ এবং স্ট্যাক থেকে পপ করুন।
5. ret উল্টে দিন (reverse) এবং রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string parseTernary(string s) {
        string ret = "";
        int n = s.size();
        stack<char> st;
        
        for (int i = n - 1; i >= 0; i--) {
            char x = s[i];
            if (!st.empty() && st.top() == '?') {
                st.pop(); // '?' বাদ দিন
                char first = st.top(); st.pop();
                st.pop(); // ':' বাদ দিন
                char second = st.top(); st.pop();
                
                if (x == 'T') {
                    st.push(first);
                } else {
                    st.push(second);
                }
            } else {
                st.push(x);
            }
        }
        
        while (!st.empty()) {
            ret += st.top();
            st.pop();
        }
        
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.parseTernary("T?T?F:T:T"); // আউটপুট: F
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: "T?T?F:T:T"
আউটপুট: F