ধরুন আমাদের কাছে একটি স্ট্রিং s আছে যেখানে অপারেটর "এবং" এবং "বা" সহ একটি বুলিয়ান এক্সপ্রেশন রয়েছে, এটি মূল্যায়ন করুন এবং ফলাফলটি ফেরত দিন। এখানে অভিব্যক্তিতে বন্ধনী থাকতে পারে, যা প্রথমে মূল্যায়ন করা উচিত।
সুতরাং, ইনপুট যদি s ="T এবং (F বা T)" এর মত হয়, তাহলে আউটপুট হবে True
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:
-
স্ট্যাক :=একটি নতুন তালিকা
-
t =ফাঁকা স্থান দ্বারা s বিভক্ত উপাদানের তালিকা
-
প্রতিটি v এর জন্য t, করুন
-
যদি v[0] হয় "(", তাহলে
-
যখন v["("-এর সূচী থেকে শেষ পর্যন্ত) "T" এর মত একই স্ট্যাকে
-
-
অন্যথায় যখন ")" পাওয়া যায়, তখন
-
ct :=v
এ ")" বন্ধনী বন্ধনীর সংখ্যা -
যখন v[সূচী ০ থেকে v - ct এর সাইজ পর্যন্ত] স্ট্যাকে "T" এর মতো হয়
-
0 থেকে ct-1 রেঞ্জের প্রতিটি মানের জন্য, করুন
-
ডান:=স্ট্যাক থেকে পপ
-
-
-
-
:=স্ট্যাক থেকে পপ
-
বাম :=স্ট্যাক থেকে পপ
-
অপারেশন করুন (বাম বা ডানে) এবং স্ট্যাকের মধ্যে পুশ করুন
-
অন্যথায় যখন v হয় "T" বা "F", তখন
-
স্ট্যাকের মধ্যে যখন v "T" এর মতো হয়
তখন ট্রু পুশ করুন
-
-
অন্যথায়,
-
অপ[ভি] স্ট্যাকের মধ্যে ঠেলে
-
-
-
যদি উপাদান স্ট্যাকের মধ্যে গণনা> 1 হয়, তাহলে
-
i এর জন্য রেঞ্জ 0 থেকে স্ট্যাকের আকার - 1, 2 দ্বারা বৃদ্ধি করুন, করুন
-
স্ট্যাক[i + 2] :=স্ট্যাক[i + 1](স্ট্যাক[i], স্ট্যাক[i + 2])
-
-
স্ট্যাকের শীর্ষ উপাদান রিটার্ন করুন
-
-
স্ট্যাকের নীচের উপাদান ফেরত দিন
আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:
উদাহরণ
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