मान लीजिए हमारे पास एक एक्सप्रेशन है जो टर्नरी एक्सप्रेशन को रखता है, हमें एक्सप्रेशन के परिणाम का मूल्यांकन करना है। यह T और F जैसे कुछ मानों को सत्य और असत्य के लिए और "?" और ":" वर्णों का समर्थन करता है। कुछ गुण हैं:
- दिए गए स्ट्रिंग की लंबाई 10000 से कम या बराबर होनी चाहिए।
- सशर्त एक्सप्रेशन दाएं से बाएं समूहित होते हैं।
- शर्त हमेशा T या F होगी। इसलिए शर्त कभी अंक नहीं होगी।
- एक्सप्रेशन का परिणाम हमेशा T या F का मूल्यांकन करेगा।
उदाहरण के लिए, यदि इनपुट "T ? T ? F : T : T" है, तो आउटपुट F होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- ret := एक खाली स्ट्रिंग, n := s का आकार,
- एक स्टैक st बनाएं
- i को n - 1 से 0 तक नीचे के लिए
- x := s[i]
- यदि st खाली नहीं है और स्टैक का शीर्ष '?' है, तो
- st से हटाएं
- first := st का शीर्ष, फिर स्टैक से दो तत्व हटाएं
- second := स्टैक का शीर्ष, और st से हटाएं
- यदि x, T है, तो first को st में डालें, अन्यथा second को st में डालें
- अन्यथा x को st में डालें
- जब तक st खाली नहीं है, करें
- ret := ret + st का शीर्ष और st से हटाएं
- ret को उल्टा करें और लौटाएं
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
#include#include #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; } }; int main(){ Solution ob; cout << (ob.parseTernary("T?T?F:T:T")); }
इनपुट
"T?T?F:T:T"
आउटपुट
F