পাইথনে বুলিয়ান এক্সপ্রেশন পার্সিং (Parsing A Boolean Expression)

সমস্যা বিবরণ

একটি বুলিয়ান এক্সপ্রেশন দেওয়া থাকে যা নিচের গ্রামার মেনে:

• "t" → True
• "f" → False
• "!(expr)" → NOT
• "&(expr1,expr2,...)" → AND
• "|(expr1,expr2,...)" → OR

উদাহরণ

expression = "|(!(t),&(t,f,t))" → আউটপুট: False

!(t)=False, &(t,f,t)=False, |(False,False)=False।

এলগরিদম (Recursive Descent Parser)

1. solve(e, i) ফাংশন: স্ট্রিং e এবং ইনডেক্স i নেয়, (result, next_index) রিটার্ন করে।
2. বেস কেস: 't' → (True, i+1), 'f' → (False, i+1)।
3. অপারেটর কেস: op = e[i] (!, &, |), i += 2 (প্যারেনথেসিস স্কিপ)।
4. স্ট্যাক দিয়ে সাব-এক্সপ্রেশন পার্স করুন ')' পাওয়া পর্যন্ত।
5. op অনুযায়ী all(stack) (AND), any(stack) (OR), not stack[0] (NOT) করুন।
6. (result, i+1) রিটার্ন।

পাইথন বাস্তবায়ন

class Solution:
    def parseBoolExpr(self, expression):
        return self.solve(expression, 0)[0]
    
    def solve(self, e, i):
        if e[i] == 'f':
            return False, i + 1
        if e[i] == 't':
            return True, i + 1
        
        op = e[i]
        i += 2  # skip op and '('
        stack = []
        while e[i] != ')':
            if e[i] == ',':
                i += 1
                continue
            res, i = self.solve(e, i)
            stack.append(res)
        
        if op == '&':
            return all(stack), i + 1
        if op == '|':
            return any(stack), i + 1
        # op == '!'
        return not stack[0], i + 1

ob = Solution()
print(ob.parseBoolExpr("|(!(t),&(t,f,t))"))  # False

ইনপুট / আউটপুট

ইনপুট: "|(!(t),&(t,f,t))"
আউটপুট: False