Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में टर्नरी एक्सप्रेशन पार्सर


मान लीजिए हमारे पास एक स्ट्रिंग है जो आर्बिट्रेरिली नेस्टेड टर्नरी एक्सप्रेशंस को दर्शाती है, हमें एक्सप्रेशन का रिजल्ट कैलकुलेट करना है। हम हमेशा मान सकते हैं कि दिया गया एक्सप्रेशन वैलिड है और केवल डिजिट्स 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

  1. - C++ में एक एक्सप्रेशन से अवैध पैरेंथेसिस को हटाना

    एक पैरेंथेसिस अनुक्रम दिया गया है; अब, आपको उन सभी संभावित पैरेंथेसिस को प्रिंट करना होगा जो यह अवैध ब्रैकेट को हटाकर बना सकता है, उदाहरण के लिए: इनपुट: str = ()())() आउटपुट: ()()() (())() दो संभावित समाधान हैं ()()() और (())() इनपुट: str = (v)())() आउटपुट: (v)()() (v())() इस समस्या में, हम बैकट्

  1. C++ में उदाहरण के साथ एक्सप्रेशन ट्री C++ में उदाहरण के साथ एक्सप्रेशन ट्री

    एक एक्सप्रेशन ट्री एक विशेष प्रकार का बाइनरी ट्री है जिसमें ट्री का प्रत्येक नोड या तो एक ऑपरेटर या ऑपरेंड से बना होता है। लीफ नोड्स ट्री के एक ऑपरेंड को दर्शाते हैं। नॉन-लीफ नोड्स ट्री के एक ऑपरेटर को दर्शाते हैं। उदाहरण: इनफिक्स एक्सप्रेशन प्राप्त करने के लिए जिसे आसानी से हल किया जा सकता है, हम

  1. C++ में एक्सप्रेशन ट्री का मूल्यांकन C++ में एक्सप्रेशन ट्री का मूल्यांकन

    इस समस्या में, हमें एक एक्सप्रेशन ट्री दिया गया है जिसमें +, -, /, * जैसे बाइनरी ऑपरेशन होते हैं। हमें इस एक्सप्रेशन ट्री का मूल्यांकन करके परिणाम वापस करना होता है। एक्सप्रेशन ट्री क्या है? एक्सप्रेशन ट्री एक विशेष प्रकार का बाइनरी ट्री है जिसमें प्रत्येक नोड या तो एक ऑपरेटर होता है या एक ऑपरेंड,