ধরুন আমাদের একটি অভিব্যক্তি আছে যা ত্রিমাত্রিক রাশি ধারণ করে, আমাদের অভিব্যক্তিটির ফলাফল মূল্যায়ন করতে হবে। এটি সত্য এবং মিথ্যার জন্য T এবং F এর মত কিছু মান সমর্থন করে এবং "?" এবং ":" অক্ষর। কিছু বৈশিষ্ট্য আছে:
- প্রদত্ত স্ট্রিংটির দৈর্ঘ্য অবশ্যই 10000 এর কম বা সমান হতে হবে।
- কন্ডিশনাল এক্সপ্রেশন ডান-থেকে-বামে গ্রুপ।
- শর্তটি সর্বদা T বা F হবে। তাই শর্তটি কখনই একটি অঙ্ক হবে না।
- অভিব্যক্তির ফলাফল সর্বদা T বা F তে মূল্যায়ন করা হবে।
সুতরাং উদাহরণস্বরূপ, যদি ইনপুটটি "T? টি? F :T :T", তাই আউটপুট হবে F.
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:
- ret :=একটি খালি স্ট্রিং, n :=s এর আকার,
- একটি স্ট্যাক স্ট্যাক তৈরি করুন
- আমি n – 1 থেকে 0
- রেঞ্জে
- x :=s[i]
- যদি st খালি না হয় এবং স্ট্যাকের উপরের '?' হয়, তাহলে
- st থেকে মুছুন
- প্রথম :=st এর শীর্ষ, তারপর স্ট্যাক থেকে দুটি উপাদান মুছে দিন
- সেকেন্ড :=স্ট্যাকের শীর্ষ, এবং st থেকে মুছে দিন
- যদি x টি হয়, তাহলে প্রথমে st-এ ঢোকান, অন্যথায় st-এ দ্বিতীয় ঢোকান
- অন্যথায় st-এ x ঢোকান
- যখন st খালি নয়, তারপর
- ret :=ret + st এর শীর্ষ এবং st থেকে মুছে দিন
- রিভার্স রেট এবং রিটার্ন রিটার্ন
আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:
উদাহরণ
#include
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack 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;
}
};
main(){
Solution ob;
cout << (ob.parseTernary("T?T?F:T:T"));
} ইনপুট
" T?T?F:T:T"
আউটপুট
F
