मान लीजिए हमारे पास एक स्ट्रिंग है जो आर्बिट्रेरिली नेस्टेड टर्नरी एक्सप्रेशंस को दर्शाती है, हमें एक्सप्रेशन का रिजल्ट कैलकुलेट करना है। हम हमेशा मान सकते हैं कि दिया गया एक्सप्रेशन वैलिड है और केवल डिजिट्स 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 का साइज, एक स्टैक 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 को रिवर्स करें और लौटाएं
उदाहरण (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("F?1:T?4:5"));
}
इनपुट
"F?1:T?4:5"
आउटपुट
4