ধরুন আমাদের একটি স্ট্রিং আছে যেটি যেকোনো নেস্টেড টার্নারি এক্সপ্রেশন রিপ্রেজেন্ট করে, আমাদের এক্সপ্রেশনটির রেজাল্ট ক্যালকুলেট করতে হবে। আমরা সবসময় ধরে নিতে পারি দেওয়া এক্সপ্রেশনটি ভ্যালিড এবং শুধু ডিজিট ০-৯, ?, :, T এবং F এই ক্যারেক্টারগুলো দিয়ে গঠিত। (এখানে T এবং F রিপ্রেজেন্ট করে True এবং False)। কিছু বৈশিষ্ট্য:
দেওয়া স্ট্রিং-এর দৈর্ঘ্য ১০০০০-এর চেয়ে বড় হবে না।
প্রতিটি সংখ্যা শুধু এক ডিজিট ধারণ করবে।
কন্ডিশনাল এক্সপ্রেশন গোষ্ঠী ডান-থেকে-বামে গ্রুপ হবে।
কন্ডিশন সবসময় T বা F হবে। তাই কন্ডিশন কখনো ডিজিট হবে না।
এক্সপ্রেশনটির রেজাল্ট সবসময় একটি ডিজিট ০-৯, T বা F-এ ইভ্যালুয়েট হবে।
উদাহরণস্বরূপ, ইনপুট “F?1:T?4:5” হলে আউটপুট হবে ৪, কারণ ডানপাশের এক্সপ্রেশন “T?4:5” পার্স করলে ৪ রিটার্ন করবে, তারপর মূল এক্সপ্রেশন হবে “F?1:4”, সুতরাং রিটার্ন ভ্যালু ৪।
সমাধানের ধাপগুলো:
ret := খালি স্ট্রিং, n := s-এর সাইজ, একটি স্ট্যাক st তৈরি করুন
i = n – 1 থেকে ০ পর্যন্ত লুপ চালান
x := s[i]
যদি st খালি নয় এবং st-এর টপ '?' হয়, তবে
st থেকে পপ করুন
first := st-এর টপ, তারপর st থেকে দুই উপাদান পপ করুন
second := st-এর টপ, এবং st থেকে পপ করুন
যদি x == 'T' হয়, তবে first st-এ পশ করুন, অন্যথায় second পশ করুন
অন্যথায়, x st-এ ইনসার্ট করুন
যখন st খালি নয়
ret := ret + st-এর টপ এবং st থেকে পপ করুন
ret রিভার্স করুন এবং রিটার্ন করুন
উদাহরণ (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
