ধরুন আমাদের দুটি বন্ধনী সিকোয়েন্স s এবং t আছে শুধুমাত্র এই '(' এবং ')' অক্ষরগুলির সাথে। আমাদের চেক করতে হবে যে s এবং t এর সংযুক্ত স্ট্রিংটি ভারসাম্যপূর্ণ কিনা। সংযোজন s | দ্বারা করা যেতে পারে t বা t | s.
সুতরাং, যদি ইনপুটটি s ="()())), t ="()(()(", তাহলে আউটপুটটি True হবে কারণ যদি আমরা t |s সংযুক্ত করি, তাহলে আমরা "() পাব। (()(()())), যা সুষম।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন is_balanced_parenthesis() সংজ্ঞায়িত করুন। এটি স্ট্রিং লাগবে
- স্ট্যাক :=একটি নতুন তালিকা
- আমি 0 থেকে স্ট্রিং এর আকারের মধ্যে,
- করুন
- যদি স্ট্রিং[i] '(' এর মত হয়, তাহলে
- স্ট্যাকের মধ্যে স্ট্রিং[i] ঠেলে
- অন্যথায়,
- যদি স্ট্যাক খালি থাকে, তাহলে
- মিথ্যে ফেরত দিন
- অন্যথায়,
- স্ট্যাক থেকে পপ
- যদি স্ট্যাক খালি থাকে, তাহলে
- যদি স্ট্রিং[i] '(' এর মত হয়, তাহলে
- যদি স্ট্যাক খালি না হয়, তাহলে
- মিথ্যে ফেরত দিন
- সত্য ফেরান
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
- যদি_ব্যালেন্সড_বন্ধনী(s + t) সত্য হয়, তাহলে
- সত্য ফেরান
- রিটার্ন হল_ব্যালেন্সড_বন্ধনী(t + s)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
def is_balanced_parenthesis(string):
stack = []
for i in range(len(string)):
if string[i] == '(':
stack.append(string[i])
else:
if len(stack) == 0:
return False
else:
stack.pop()
if len(stack) > 0:
return False
return True
def solve(s, t):
if is_balanced_parenthesis(s + t):
return True
return is_balanced_parenthesis(t + s)
s = "()()))"
t = "()(()("
print(solve(s, t)) ইনপুট
"()()))", "()(()(") আউটপুট
True
