পাইথনে স্ট্রিং থেকে বুলিয়ান এক্সপ্রেশন ইভ্যালুয়েট করার প্রোগ্রাম

ধরা যাক s নামক একটি স্ট্রিং রয়েছে যেটিতে "and" এবং "or" অপারেটরসহ একটি বুলিয়ান এক্সপ্রেশন রয়েছে। এটিকে ইভ্যালুয়েট করে ফলাফল ফেরত দিতে হবে। এক্সপ্রেশনে প্যারেনথেসিস থাকতে পারে, যেগুলোকে প্রথমে ইভ্যালুয়েট করতে হবে।

উদাহরণ

ইনপুট: s = "T and (F or T)"

আউটপুট: True

সমাধানের ধাপসমূহ

1. stack := একটি নতুন লিস্ট
2. t := s.split() (ব্ল্যাঙ্ক স্পেস দিয়ে আলাদা করা টোকেনগুলির লিস্ট)
3. প্রতিটি v এর জন্য t-এ:
   • যদি v[0] == "(" হয়, তবে:
     • স্ট্যাকে True পুশ করুন যদি v[v.count("("):] == "T" হয়
   • অন্যথায় যদি ")" পাওয়া যায়, তবে:
     • ct := v-এ বন্ধ প্যারেনথেসিস ")" এর সংখ্যা
     • স্ট্যাকে True পুশ করুন যদি v[:-ct] == "T" হয়
     • ct বার লুপ চালান:
       • right := stack.pop()
       • o := stack.pop() (অপারেটর)
       • left := stack.pop()
       • stack.append(o(left, right))
   • অন্যথায় যদি v "T" বা "F" হয়, তবে:
     • স্ট্যাকে True পুশ করুন যদি v == "T" হয়
   • অন্যথায় (অপারেটর হলে):
     • stack.append(op[v])
4. যদি স্ট্যাকে ১-এর বেশি এলিমেন্ট থাকে, তবে:
   • i = 0 থেকে len(stack)-1 পর্যন্ত ২-র গুনে বাড়িয়ে লুপ চালান
   • stack[i+2] := stack[i+1](stack[i], stack[i+2])
   • স্ট্যাকের টপ এলিমেন্ট ফেরত দিন
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()
s = "T and (F or T)"
print(ob.solve(s))

ইনপুট

"T and (F or T)"

আউটপুট

True