पायथन में स्ट्रिंग से बूलियन अभिव्यक्ति का मूल्यांकन करने का प्रोग्राम

एक स्ट्रिंग s दी गई है जिसमें बूलियन अभिव्यक्ति है जिसमें ऑपरेटर "and" और "or" हैं, और कोष्ठक हो सकते हैं। अभिव्यक्ति का मूल्यांकन करके परिणाम वापस करें।

उदाहरण

इनपुट: s = "T and (F or T)"

आउटपुट: True

एल्गोरिदम (स्टैक आधारित पार्सिंग)

1. एक स्टैक stack बनाएं।
2. स्ट्रिंग को स्पेस से विभाजित करके टोकन प्राप्त करें।
3. प्रत्येक टोकन v के लिए:
   • यदि v '(' से शुरू होता है: खोलने वाले कोष्ठक की संख्या गिनें, आंतरिक मान ("T" या "F") को बूलियन में बदलकर स्टैक पर पुश करें।
   • यदि v में ')' है: बंद कोष्ठक की संख्या ct गिनें। आंतरिक मान को बूलियन में बदलकर पुश करें। फिर ct बार: दायां ऑपरेंड पॉप करें, ऑपरेटर पॉप करें, बायां ऑपरेंड पॉप करें, ऑपरेशन लागू करें, परिणाम पुश करें।
   • यदि v "T" या "F" है: संबंधित बूलियन पुश करें।
   • अन्यथा (ऑपरेटर "and"/"or"): संबंधित लैम्ब्डा फंक्शन पुश करें।
4. अंत में, यदि स्टैक में एक से अधिक तत्व हैं, तो बाएं से दाएं मूल्यांकन करें (क्योंकि सभी ऑपरेटर समान प्राथमिकता के हैं और बाएं-संयोजक हैं)।
5. स्टैक का शीर्ष तत्व वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, s):
        stack = []
        op = {
            "or": lambda x, y: x or y,
            "and": lambda x, y: x and y,
        }
        for v in s.split():
            if v[0] == "(":
                # खोलने वाले कोष्ठक छोड़कर मान लें
                stack.append(v[v.count("("):] == "T")
            elif v.count(")") > 0:
                ct = v.count(")")
                # बंद कोष्ठक छोड़कर मान लें
                stack.append(v[:-ct] == "T")
                for _ in range(ct):
                    right = stack.pop()
                    o = stack.pop()
                    left = stack.pop()
                    stack.append(o(left, right))
            elif v in ["T", "F"]:
                stack.append(v == "T")
            else:
                stack.append(op[v])
        
        # शेष स्टैक का मूल्यांकन (बाएं से दाएं)
        if len(stack) > 1:
            for i in range(0, len(stack) - 1, 2):
                stack[i + 2] = stack[i + 1](stack[i], stack[i + 2])
            return stack[-1]
        return stack[0]

# परीक्षण
ob = Solution()
print(ob.solve("T and (F or T)"))        # True
print(ob.solve("F or T and F"))          # False
print(ob.solve("(T or F) and (F or T)")) # True

समय जटिलता

• O(n) जहां n टोकन की संख्या है।
• स्थान: O(n) स्टैक के लिए।

नोट

यह कार्यान्वयन मानता है कि इनपुट वैध है और ऑपरेटर "and", "or" और कोष्ठक सही ढंग से संतुलित हैं। "and" और "or" की समान प्राथमिकता मानी गई है (बाएं-संयोजक)।