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

ধরুন আমাদের একটি বুলিয়ান এক্সপ্রেশন আছে, আমাদের সেই এক্সপ্রেশনের মূল্যায়ন করার পর ফলাফল বের করতে হবে।

একটি অভিব্যক্তি হয় −

• "t", সত্যে মূল্যায়ন;

• "f", False এ মূল্যায়ন করা;

• "!(অভিব্যক্তি)", অভ্যন্তরীণ অভিব্যক্তির যৌক্তিক নয় বলে মূল্যায়ন করা;

• "&(expr1,expr2,...)", 2 বা তার বেশি অভ্যন্তরীণ অভিব্যক্তির যৌক্তিক AND মূল্যায়ন করা;

• "|(expr1,expr2,...)", 2 বা তার বেশি অভ্যন্তরীণ অভিব্যক্তির যৌক্তিক OR মূল্যায়ন করা;

সুতরাং, যদি ইনপুট "|(!(t),&(t,f,t))" এর মত হয়, তাহলে আউটপুট হবে fasle, এর কারণ !(t) মিথ্যা, তারপর &(t,f, t) এছাড়াও মিথ্যা, তাই সমস্ত মিথ্যা মানের OR মিথ্যা হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• সংজ্ঞায়িত সমাধান(), এটি ই, i

  লাগবে

• যদি e[i] "f" এর মত হয়, তাহলে −

  • রিটার্ন (মিথ্যা, i + 1)

• অন্যথায় যখন e[i] "t" -

  এর মত হয়

• রিটার্ন (সত্য, i + 1)

• op :=e[i], i :=i + 2

• একটি স্ট্যাক সংজ্ঞায়িত করুন

• যখন e[i] বন্ধনী বন্ধ করছে না, −

  করুন

  • যদি e[i] "," এর মত হয়, তাহলে -

    • i :=i + 1

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • res,i :=সমাধান (e, i)

  • স্ট্যাকের মধ্যে পুশ res

• op যদি "&" এর মত হয়, তাহলে −

  • স্ট্যাকের সমস্ত উপাদান সত্য হলে সত্য ফেরত দিন, অন্যথায় মিথ্যা, i + 1

• অন্যথায় যখন op " OR " -

  এর মত হয়

  • স্ট্যাকের মধ্যে অন্তত একটি উপাদান সত্য হলে সত্য ফেরত দিন, অন্যথায় মিথ্যা, i + 1

• রিটার্ন (স্ট্যাকের বিপরীত [0], i + 1)

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• s,y :=সমাধান করুন(এক্সপ্রেশন, 0)

• s

  ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution(object):
   def parseBoolExpr(self, expression):
      s,y = self.solve(expression,0)
      return s
   def solve(self,e,i):
      if e[i] =="f":
         return False,i+1
      elif e[i] == "t":
         return True,i+1
      op = e[i]
      i = i+2
      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
      elif op == "|":
         return any(stack),i+1
      return not stack[0],i+1
ob = Solution()
print(ob.parseBoolExpr("|(!(t),&(t,f,t))"))

ইনপুট

"|(!(t),&(t,f,t))"

আউটপুট

False