পাইথনে সঠিক প্যারেনথেসিস बनाने জন্য ন্যূনতম সরানো প্রয়োজনীয় সংখ্যা খুঁজে বের করার প্রোগ্রাম

আমাদের একটি স্ট্রিং s আছে যাতে '(', ')' এবং ছোট হাতের ইংরেজি অক্ষর রয়েছে। আমাদের ন্যূনতম সংখ্যক প্যারেনথেসিস ('(' বা ')', যেকোনো পজিশন থেকে) মুছে দিতে হবে যাতে ফলাফলটি একটি সঠিক প্যারেনথেসিস স্ট্রিং হয় এবং শেষে যেকোনো একটি সঠিক স্ট্রিং রিটার্ন করতে হবে। এখানে প্যারেনথেসিস স্ট্রিং সঠিক হবে যদি নিচের শর্তগুলো পূরণ হয়:

• স্ট্রিংটি খালি এবং শুধু ছোট হাতের অক্ষর ধারণ করে, অথবা

• স্ট্রিংটি AB আকারে লেখা যায় (A এবং B কনক্যাটেনেটেড), যেখানে A এবং B সঠিক স্ট্রিং, অথবা

• স্ট্রিংটি (A) আকারে লেখা যায়, যেখানে A একটি সঠিক স্ট্রিং।

উদাহরণস্বরূপ, ইনপুট s = "m)n(o)p" হলে আউটপুট হবে "mn(o)p"।

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

• stack := একটি নতুন লিস্ট

• indexes := একটি নতুন সেট

• i := 0

• s-এর প্রতিটি c এর জন্য:

  • যদি c == '(' হয়, তবে:

    • i-কে stack-এ পুশ করুন

  • অন্যথায়, যদি c == ')' হয়, তবে:

    • যদি stack-এর আকার 0 হয়, তবে:

      • i-কে indexes-এ যোগ করুন

    • অন্যথায়:

      • stack-এ থেকে পপ করুন

  • i := i + 1

• ret := খালি স্ট্রিং

• indexes := indexes.union(stack)

• i = 0 থেকে s-এর আকার - 1 পর্যন্ত লুপ চালান:

  • যদি i not in indexes হয়, তবে:

    • ret := ret + s[i]

• ret রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

def solve(s):
    stack = []
    indexes = set()
    i = 0
    for c in s:
        if c == '(':
            stack.append(i)
        elif c == ')':
            if len(stack) == 0:
                indexes.add(i)
            else:
                stack.pop()
        i += 1
    ret = ''
    indexes = indexes.union(stack)
    for i in range(len(s)):
        if i not in indexes:
            ret += s[i]
    return ret

s = "m)n(o)p"
print(solve(s))

ইনপুট

"m)n(o)p"

আউটপুট

mn(o)p