मान लीजिए कि हमारे पास एक स्ट्रिंग है जो मनमाने ढंग से नेस्टेड टर्नरी एक्सप्रेशन का प्रतिनिधित्व करती है, हमें एक्सप्रेशन के परिणाम की गणना करनी होगी। हम हमेशा यह मान सकते हैं कि दिया गया व्यंजक वैध है और इसमें केवल 0-9, ?, :, T और F ये कुछ वर्ण हैं। (यहाँ T और F क्रमशः सत्य और असत्य का प्रतिनिधित्व करते हैं)। कुछ गुण हैं -
-
दी गई स्ट्रिंग की लंबाई 10000 से कम या उसके बराबर होनी चाहिए।
-
प्रत्येक संख्या में केवल एक अंक होगा।
-
सशर्त अभिव्यक्ति समूह दाएं से बाएं।
-
कंडीशन हमेशा या तो T या F होगी। इसलिए कंडीशन कभी भी डिजिट नहीं होगी।
-
व्यंजक का परिणाम हमेशा 0-9 अंक, T या F में से किसी एक का मूल्यांकन करेगा।
तो उदाहरण के लिए, यदि इनपुट "एफ? 1:टी? 4:5" जैसा है, तो आउटपुट 4 होगा, क्योंकि यह सबसे सही अभिव्यक्ति "टी? 4:5" को पार्स करेगा, यह 4 लौटाएगा, फिर मुख्य अभिव्यक्ति "F?1:4" होगी, इसलिए लौटाया गया मान 4 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
ret :=एक खाली स्ट्रिंग, n :=s का आकार, एक स्टैक st बनाएं
-
मैं के लिए n - 1 से 0 तक की श्रेणी में हूं
-
एक्स:=एस [i]
-
यदि सेंट खाली नहीं है और स्टैक का शीर्ष '?' है, तो
-
सेंट से हटाएं
-
पहले:=सेंट के ऊपर, फिर स्टैक से दो तत्वों को हटा दें
-
दूसरा:=स्टैक के ऊपर, और सेंट से हटाएं
-
यदि x, T है, तो पहले st में डालें, अन्यथा st में दूसरा डालें
-
-
अन्यथा, x को सेंट में डालें
-
-
जबकि सेंट खाली नहीं है, तब
-
रिट :=रिट + सेंट के ऊपर और सेंट से हटाएं
-
-
रिवर्स रिट और रिटर्न रिट
उदाहरण (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