ধরুন আমাদের কাছে একটি স্ট্রিং আছে যা ইচ্ছামত নেস্টেড টারনারি এক্সপ্রেশনের প্রতিনিধিত্ব করে, আমাদের এক্সপ্রেশনের ফলাফল গণনা করতে হবে। আমরা সর্বদা ধরে নিতে পারি যে প্রদত্ত অভিব্যক্তিটি বৈধ এবং শুধুমাত্র 0-9, ?, :, T এবং F এই কয়েকটি অক্ষর নিয়ে গঠিত। (এখানে T এবং F যথাক্রমে True এবং False প্রতিনিধিত্ব করে)। কিছু বৈশিষ্ট্য আছে -
-
প্রদত্ত স্ট্রিং এর দৈর্ঘ্য 10000 এর কম বা সমান হতে হবে।
-
প্রতিটি সংখ্যায় শুধুমাত্র একটি সংখ্যা থাকবে।
-
কন্ডিশনাল এক্সপ্রেশন ডান-থেকে-বামে গ্রুপ।
-
শর্তটি সর্বদা T বা F হবে। তাই শর্তটি কখনই একটি অঙ্ক হবে না।
-
অভিব্যক্তির ফলাফল সর্বদা 0-9, T বা F সংখ্যায় মূল্যায়ন করবে।
সুতরাং উদাহরণস্বরূপ, যদি ইনপুটটি "F?1:T?4:5" এর মত হয়, তাহলে আউটপুট হবে 4, কারণ এটি ডানদিকের অভিব্যক্তি "T?4:5" পার্স করবে, এটি 4 প্রদান করবে, তারপর প্রধান অভিব্যক্তি হবে “F?1:4”, তাই প্রত্যাবর্তিত মান হল 4।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=একটি খালি স্ট্রিং, n :=s এর আকার, একটি স্ট্যাক স্ট্যাক তৈরি করুন
-
I রেঞ্জ n – 1 থেকে 0
এর মধ্যে-
x :=s[i]
-
যদি st খালি না হয় এবং স্ট্যাকের উপরের '?' হয়, তাহলে
-
st
থেকে মুছুন -
প্রথমে :=st এর শীর্ষ, তারপর স্ট্যাক থেকে দুটি উপাদান মুছে দিন
-
দ্বিতীয় :=স্ট্যাকের উপরে, এবং st
থেকে মুছে দিন -
যদি x টি হয়, তাহলে প্রথমে st-এ ঢোকান, অন্যথায় st-এ দ্বিতীয় ঢোকান
-
-
অন্যথায়, st
-এ x ঢোকান
-
-
যখন st খালি নয়, তারপর
-
ret :=ret + st এর শীর্ষ এবং st থেকে মুছুন
-
-
রিভার্স রেট এবং রিটার্ন রিটার্ন
উদাহরণ (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;
}
};
main(){
Solution ob;
cout << (ob.parseTernary("F?1:T?4:5"));
} ইনপুট
"F?1:T?4:5"
আউটপুট
4
